Złożoność obliczeniowa/Test 12: Problemy funkcyjne i złożoność zliczania

From Studia Informatyczne

Problem FSAT polega na:

odpowiedzi na pytanie czy formuła jest tautologią

znalezieniu wartościowania spełniającego formułę

znalezieniu formuły równoważnej

odpowiedzi na pytanie czy formuła jest spełnialna

obliczeniu liczby rozwiązań spełniających formułę


Klasę \cc{FNP} definiujemy przy pomocy:

relacji liniowo zrównoważonej

relacji wielomianowo rozstrzygalnej

dowolnej relacji binarnej

relacji wielomianowo zrównoważonej


Klasa \cc{TFNP} to:

podzbiór klasy \cc{FNP}

podzbiór klasy \cc{FP}

klasa problemów funkcyjnych, w których rozwiązanie zawsze istnieje

klasa problemów definiowanych na liczbach całkowitych


Która z poniższych implikacji jest prawdziwa?

\cc{FP}=\cc{FNP} \Leftarrow \cc{P}=\cc{NP}

\cc{P}=\cc{NP} \Leftarrow \cc{FP}=\cc{FNP}

obydwie

żadna


Problem ANOTHER HAMILTON CYCLE

należy do klasy \cc{FP}

należy do klasy \cc{FNP}

\cc{FNP}-zupełny

należy do klasy \cc{TFNP}


Problem PERMANENT

to inna nazwa dla problemu \# MATCHING

jest wielomianowy

polega na obliczaniu permanentu macierzy

jest \#\cc{P}-zupełny


Twierdzenie Valianta mówi o tym, że:

problem PERMANENT należy do \#\cc{P}

problem \# SAT jest \#\cc{P}-zupełny

problem \# HAMILTONIAN PATH jest \#\cc{P}-zupełny

problem \# SAT należy do \#\cc{P}

problem PERMANENT jest \#\cc{P}-zupełny