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

Problem FSAT polega na:

odpowiedzi na pytanie czy formuła jest tautologią Źle

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

znalezieniu formuły równoważnej Źle

odpowiedzi na pytanie czy formuła jest spełnialna Źle

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

Klasę $\mathrm {FNP}$ definiujemy przy pomocy:

relacji liniowo zrównoważonej Źle

relacji wielomianowo rozstrzygalnej Dobrze

dowolnej relacji binarnej Źle

relacji wielomianowo zrównoważonej Dobrze

Klasa $\mathrm {TFNP}$ to:

podzbiór klasy $\mathrm {FNP}$ Dobrze

podzbiór klasy $\mathrm {FP}$ Źle

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

klasa problemów definiowanych na liczbach całkowitych Źle

Która z poniższych implikacji jest prawdziwa?

$\mathrm {FP} =\mathrm {FNP} \Leftarrow \mathrm {P} =\mathrm {NP}$ Źle

$\mathrm {P} =\mathrm {NP} \Leftarrow \mathrm {FP} =\mathrm {FNP}$ Źle

obydwie Dobrze

żadna Źle

Problem ANOTHER HAMILTON CYCLE

należy do klasy $\mathrm {FP}$ Źle

należy do klasy $\mathrm {FNP}$ Dobrze

$\mathrm {FNP}$-zupełny Dobrze

należy do klasy $\mathrm {TFNP}$ Źle

Problem PERMANENT

to inna nazwa dla problemu $\#$ MATCHING Dobrze

jest wielomianowy Źle

polega na obliczaniu permanentu macierzy Dobrze

jest $\#\mathrm {P}$-zupełny Dobrze

Twierdzenie Valianta mówi o tym, że:

problem PERMANENT należy do $\#\mathrm {P}$ Źle

problem $\#$ SAT jest $\#\mathrm {P}$-zupełny Źle

problem $\#$ HAMILTONIAN PATH jest $\#\mathrm {P}$-zupełny Źle

problem $\#$ SAT należy do $\#\mathrm {P}$ Źle

problem PERMANENT jest $\#\mathrm {P}$-zupełny Dobrze