Złożoność obliczeniowa/Test 12: Problemy funkcyjne i złożoność zliczania: Różnice pomiędzy wersjami

Z Studia Informatyczne
Przejdź do nawigacjiPrzejdź do wyszukiwania
← poprzednia edycja
WizualnieWikikod
Rogoda (dyskusja | edycje)
1875 edycji
Nie podano opisu zmian
m Zastępowanie tekstu - "\cc{" na "\mathrm{"
 
Linia 10: Linia 10:


<quiz>
<quiz>
Klasę <math>\cc{FNP}</math> definiujemy przy pomocy:  
Klasę <math>\mathrm{FNP}</math> definiujemy przy pomocy:  
<wrongoption>relacji liniowo zrównoważonej</wrongoption>
<wrongoption>relacji liniowo zrównoważonej</wrongoption>
<rightoption>relacji wielomianowo rozstrzygalnej</rightoption>
<rightoption>relacji wielomianowo rozstrzygalnej</rightoption>
Linia 19: Linia 19:


<quiz>
<quiz>
Klasa <math>\cc{TFNP}</math> to:  
Klasa <math>\mathrm{TFNP}</math> to:  
<rightoption>podzbiór klasy <math>\cc{FNP}</math></rightoption>
<rightoption>podzbiór klasy <math>\mathrm{FNP}</math></rightoption>
<wrongoption>podzbiór klasy <math>\cc{FP}</math></wrongoption>
<wrongoption>podzbiór klasy <math>\mathrm{FP}</math></wrongoption>
<rightoption>klasa problemów funkcyjnych, w których rozwiązanie zawsze istnieje</rightoption>
<rightoption>klasa problemów funkcyjnych, w których rozwiązanie zawsze istnieje</rightoption>
<wrongoption>klasa problemów definiowanych na liczbach całkowitych</wrongoption>
<wrongoption>klasa problemów definiowanych na liczbach całkowitych</wrongoption>
Linia 29: Linia 29:
<quiz>
<quiz>
Która z poniższych implikacji jest prawdziwa?  
Która z poniższych implikacji jest prawdziwa?  
<wrongoption><math>\cc{FP}=\cc{FNP} \Leftarrow \cc{P}=\cc{NP}</math></wrongoption>
<wrongoption><math>\mathrm{FP}=\mathrm{FNP} \Leftarrow \mathrm{P}=\mathrm{NP}</math></wrongoption>
<wrongoption><math>\cc{P}=\cc{NP} \Leftarrow \cc{FP}=\cc{FNP}</math></wrongoption>
<wrongoption><math>\mathrm{P}=\mathrm{NP} \Leftarrow \mathrm{FP}=\mathrm{FNP}</math></wrongoption>
<rightoption>obydwie</rightoption>
<rightoption>obydwie</rightoption>
<wrongoption>żadna</wrongoption>
<wrongoption>żadna</wrongoption>
Linia 38: Linia 38:
<quiz>
<quiz>
Problem ANOTHER HAMILTON CYCLE  
Problem ANOTHER HAMILTON CYCLE  
<wrongoption>należy do klasy <math>\cc{FP}</math></wrongoption>
<wrongoption>należy do klasy <math>\mathrm{FP}</math></wrongoption>
<rightoption>należy do klasy <math>\cc{FNP}</math></rightoption>
<rightoption>należy do klasy <math>\mathrm{FNP}</math></rightoption>
<rightoption><math>\cc{FNP}</math>-zupełny</rightoption>
<rightoption><math>\mathrm{FNP}</math>-zupełny</rightoption>
<wrongoption>należy do klasy <math>\cc{TFNP}</math></wrongoption>
<wrongoption>należy do klasy <math>\mathrm{TFNP}</math></wrongoption>
</quiz>
</quiz>


Linia 50: Linia 50:
<wrongoption>jest wielomianowy</wrongoption>
<wrongoption>jest wielomianowy</wrongoption>
<rightoption>polega na obliczaniu permanentu macierzy</rightoption>
<rightoption>polega na obliczaniu permanentu macierzy</rightoption>
<rightoption>jest <math>\#\cc{P}</math>-zupełny</rightoption>
<rightoption>jest <math>\#\mathrm{P}</math>-zupełny</rightoption>
</quiz>
</quiz>


Linia 56: Linia 56:
<quiz>
<quiz>
Twierdzenie Valianta mówi o tym, że:  
Twierdzenie Valianta mówi o tym, że:  
<wrongoption>problem PERMANENT należy do <math>\#\cc{P}</math></wrongoption>
<wrongoption>problem PERMANENT należy do <math>\#\mathrm{P}</math></wrongoption>
<wrongoption>problem <math>\#</math> SAT jest <math>\#\cc{P}</math>-zupełny</wrongoption>
<wrongoption>problem <math>\#</math> SAT jest <math>\#\mathrm{P}</math>-zupełny</wrongoption>
<wrongoption>problem <math>\#</math> HAMILTONIAN PATH  jest <math>\#\cc{P}</math>-zupełny</wrongoption>
<wrongoption>problem <math>\#</math> HAMILTONIAN PATH  jest <math>\#\mathrm{P}</math>-zupełny</wrongoption>
<wrongoption>problem <math>\#</math> SAT należy do <math>\#\cc{P}</math></wrongoption>
<wrongoption>problem <math>\#</math> SAT należy do <math>\#\mathrm{P}</math></wrongoption>
<rightoption>problem PERMANENT jest <math>\#\cc{P}</math>-zupełny</rightoption>
<rightoption>problem PERMANENT jest <math>\#\mathrm{P}</math>-zupełny</rightoption>
</quiz>
</quiz>

Aktualna wersja na dzień 23:29, 11 cze 2020

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ę FNP definiujemy przy pomocy:

relacji liniowo zrównoważonej

relacji wielomianowo rozstrzygalnej

dowolnej relacji binarnej

relacji wielomianowo zrównoważonej


Klasa TFNP to:

podzbiór klasy FNP

podzbiór klasy 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?

FP=FNP⇐P=NP

P=NP⇐FP=FNP

obydwie

żadna


Problem ANOTHER HAMILTON CYCLE

należy do klasy FP

należy do klasy FNP

FNP-zupełny

należy do klasy TFNP


Problem PERMANENT

to inna nazwa dla problemu # MATCHING

jest wielomianowy

polega na obliczaniu permanentu macierzy

jest #P-zupełny


Twierdzenie Valianta mówi o tym, że:

problem PERMANENT należy do #P

problem # SAT jest #P-zupełny

problem # HAMILTONIAN PATH jest #P-zupełny

problem # SAT należy do #P

problem PERMANENT jest #P-zupełny

Źródło: „https://wazniak.mimuw.edu.pl/index.php?title=Złożoność_obliczeniowa/Test_12:_Problemy_funkcyjne_i_złożoność_zliczania&oldid=77680”