„Algoritmuselmélet - Vizsga, 2013.06.06.” változatai közötti eltérés
| 237. sor: | 237. sor: | ||
<big>'''A feladat megoldása: '''<br><br></big> | <big>'''A feladat megoldása: '''<br><br></big> | ||
Tétel: Ha X | Tétel: Ha X ≺ Y és Y ∈ NP,akkor X ∈ NP | ||
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. | ||