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

From Studia Informatyczne

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

P \neq NP

NP \neq PSPACE

P \neq UP

UP \neq NP

FP \neq FNP


W systemie dowodów interaktywnych:

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

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

V ma do dyspozycji słowo losowe

funkcja P należy do klasy FNP

P ma do dyspozycji słowo losowe

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


Problem NON-GRAPH-ISO:

należy do klasy PSPACE

nie należy do klasy coNP

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


Klasa IP:

zawiera klasę BPP

nie wiadomo czy zawiera klasę NP

zawiera klasę P

jest zawarta w klasie IP

jest domknięta na redukcje wielomianowe w sensie Karpa

nie jest domknięta na redukcje logarytmiczne


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

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

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

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

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