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 N P$ Dobrze

$N P \neq P S P A C E$ Źle

$P \neq U P$ Dobrze

$U P \neq N P$ Źle

$F P \neq F N P$ 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 $N O N - G R A P H - I S O$ :

należy do klasy $P S P A C E$ Dobrze

nie należy do klasy $c o N P$ Źle

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

Klasa $I P$ :

zawiera klasę $B P P$ Dobrze

nie wiadomo czy zawiera klasę $N P$ Źle

zawiera klasę $P$ Dobrze

jest zawarta w klasie $I P$ 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 $ϕ$ w wyniku arytmetyzacji, to:

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

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

spośród wszystkich wielomianów dających takie sam wartości co $ϕ$ 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 $ϕ$ Źle

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

Menu nawigacyjne