Złożoność obliczeniowa/Test 15: Kryptografia a złożoność

Które z poniższych zdań są warunkami koniecznymi istnienia funkcji jednokierunkowych?

$P\neq NP$ Dobrze

$NP\neq PSPACE$ Źle

$P\neq UP$ Dobrze

$UP\neq NP$ Źle

$FP\neq FNP$ Dobrze

W systemie dowodów interaktywnych:

$P$ ({\it prover}) decyduje o akceptacji słowa Źle

$V$ ({\it verifier}) ma do dyspozycji historię przesłanych dotychczas komunikatów Dobrze

$V$ ma do dyspozycji słowo losowe Dobrze

funkcja $P$ należy do klasy FNP Źle

$P$ ma do dyspozycji słowo losowe Źle

akceptacja słowa wejściowego jest zdeterminowana przez to słowo oraz przez słowo losowe Dobrze

Problem $NON-GRAPH-ISO$:

należy do klasy $PSPACE$ Dobrze

nie należy do klasy $coNP$ Źle

może zostać rozwiązany w czasie wielomianowym przez system dowodów interaktywnych Dobrze

Klasa $IP$:

zawiera klasę $BPP$ Dobrze

nie wiadomo czy zawiera klasę $NP$ Źle

zawiera klasę $P$ Dobrze

jest zawarta w klasie $IP$ Dobrze

jest domknięta na redukcje wielomianowe w sensie Karpa Dobrze

nie jest domknięta na redukcje logarytmiczne Źle

Jeżeli wielomian $W$ został otrzymany ze zmiennej $\phi$ w wyniku arytmetyzacji, to:

stopień każdej zmiennej w wielomianie $W$ jest nie większy niż liczba zmiennych występujących w $\phi$ Źle

dla argumentów Boole'owskich wartości $W$ i $\phi$ są takie same Dobrze

spośród wszystkich wielomianów dających takie sam wartości co $\phi$ dla argumentów Boole'owskich $W$ ma najmniejszą ilość wyrazów Źle

ilość wyrazów wielomianu $W$ jest liniowo zależna od długości formuły $\phi$ Źle

można obliczyć wartość wielomianu $W$ dla argumentów Boole'owskich w czasie wielomianowo zależnym od długości formuły $\phi$ Dobrze