„Rendszeroptimalizálás, 13. tétel” változatai közötti eltérés
Részletes példa futás kidolgozásának hozzáadása |
|||
| 5. sor: | 5. sor: | ||
*Lemma*: MPP<sub>k</sub> NP-beli, mert tanú rá egy particionálás, és a tanú lineáris időben ellenőrizhető. <br> | *Lemma*: MPP<sub>k</sub> NP-beli, mert tanú rá egy particionálás, és a tanú lineáris időben ellenőrizhető. <br> | ||
*Lemma*: MPP<sub>k</sub> coNP-beli, mert tanú rá egy X⊆E halmaz, ami biztosan összefüggő az összegben, azaz ∑r<sub>i</sub>(X)<|X. | *Lemma*: MPP<sub>k</sub> coNP-beli, mert tanú rá egy X⊆E halmaz, ami biztosan összefüggő az összegben, azaz ∑r<sub>i</sub>(X)<|X|. | ||
===Algoritmus=== | ===Algoritmus=== | ||