„Algoritmuselmélet - Vizsga, 2013.06.06.” változatai közötti eltérés
aNincs szerkesztési összefoglaló |
|||
| 232. sor: | 232. sor: | ||
<big>'''SAT probléma? '''<br><br></big> | <big>'''SAT probléma? '''<br><br></big> | ||
A SAT probléma NP-teljes.<br> | |||
forrás:http://www.cs.bme.hu/algel/12elo-2012.pdf<br> | |||
}} | }} | ||
<big>'''A feladat megoldása: '''<br><br></big> | <big>'''A feladat megoldása: '''<br><br></big> | ||
Tétel: Ha X -< Y és Y NP beli,akkor X is NP (-< a Karp redukciót jelenti) <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. | |||
}} | }} | ||