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ą
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ę Parser nie mógł rozpoznać (nieznana funkcja „\cc”): {\displaystyle \cc{FNP}}
definiujemy przy pomocy:
relacji liniowo zrównoważonej
relacji wielomianowo rozstrzygalnej
dowolnej relacji binarnej
relacji wielomianowo zrównoważonej
Klasa Parser nie mógł rozpoznać (nieznana funkcja „\cc”): {\displaystyle \cc{TFNP}}
to:
podzbiór klasy Parser nie mógł rozpoznać (nieznana funkcja „\cc”): {\displaystyle \cc{FNP}}
podzbiór klasy Parser nie mógł rozpoznać (nieznana funkcja „\cc”): {\displaystyle \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?
Parser nie mógł rozpoznać (nieznana funkcja „\cc”): {\displaystyle \cc{FP}=\cc{FNP} \Leftarrow \cc{P}=\cc{NP}}
Parser nie mógł rozpoznać (nieznana funkcja „\cc”): {\displaystyle \cc{P}=\cc{NP} \Leftarrow \cc{FP}=\cc{FNP}}
obydwie
żadna
Problem ANOTHER HAMILTON CYCLE
należy do klasy Parser nie mógł rozpoznać (nieznana funkcja „\cc”): {\displaystyle \cc{FP}}
należy do klasy Parser nie mógł rozpoznać (nieznana funkcja „\cc”): {\displaystyle \cc{FNP}}
Parser nie mógł rozpoznać (nieznana funkcja „\cc”): {\displaystyle \cc{FNP}} -zupełny
należy do klasy Parser nie mógł rozpoznać (nieznana funkcja „\cc”): {\displaystyle \cc{TFNP}}
Problem PERMANENT
to inna nazwa dla problemu MATCHING
jest wielomianowy
polega na obliczaniu permanentu macierzy
jest Parser nie mógł rozpoznać (nieznana funkcja „\cc”): {\displaystyle \#\cc{P}} -zupełny
Twierdzenie Valianta mówi o tym, że:
problem PERMANENT należy do Parser nie mógł rozpoznać (nieznana funkcja „\cc”): {\displaystyle \#\cc{P}}
problem SAT jest Parser nie mógł rozpoznać (nieznana funkcja „\cc”): {\displaystyle \#\cc{P}} -zupełny
problem HAMILTONIAN PATH jest Parser nie mógł rozpoznać (nieznana funkcja „\cc”): {\displaystyle \#\cc{P}} -zupełny
problem SAT należy do Parser nie mógł rozpoznać (nieznana funkcja „\cc”): {\displaystyle \#\cc{P}}
problem PERMANENT jest Parser nie mógł rozpoznać (nieznana funkcja „\cc”): {\displaystyle \#\cc{P}} -zupełny
