„Algoritmuselmélet - Vizsga, 2013.06.06.” változatai közötti eltérés
| 194. sor: | 194. sor: | ||
##Ha <math>y \ge 3</math>, akkor a DC oldal kiesik, a maradék 2 élt 2 féleképpen veheti fel, így 12 féleképpen futhat az algoritmus.}} | ##Ha <math>y \ge 3</math>, akkor a DC oldal kiesik, a maradék 2 élt 2 féleképpen veheti fel, így 12 féleképpen futhat az algoritmus.}} | ||
===7. Feladat=== | ===7. Feladat=== (Van megoldás) | ||
Létezik-e olyan X eldöntési probléma, amire X<big>∉</big>NP és X<big>≺</big>SAT egyszerre fennáll? | Létezik-e olyan X eldöntési probléma, amire X<big>∉</big>NP és X<big>≺</big>SAT egyszerre fennáll? | ||
| 237. sor: | 237. sor: | ||
<big>'''A feladat megoldása: '''<br><br></big> | <big>'''A feladat megoldása: '''<br><br></big> | ||
Tétel: Ha X ≺ Y és Y ∈ NP,akkor X ∈ NP | Tétel: Ha X ≺ Y és Y ∈ NP,akkor X ∈ NP<br> | ||
Tétel: A SAT probléma NP teljes, tehát része NP-nek.<br> | Tétel: A SAT probléma NP teljes, tehát része NP-nek.<br> | ||
A fentiek alapján, mivel X<big>∉</big>NP, a kérdéses X probléma nem létezhet. | A fentiek alapján, mivel X<big>∉</big>NP, a kérdéses X probléma nem létezhet. | ||