Tirohia te wāhanga i raro nei, ka whakahoki i te pātai i muri i roto i te reo ano rite te wāhanga: Passage: I whakaaturia e Ladner e ki te P ≠ NP ka i reira ngā raruraru i roto i te NP e kore e i roto i te P e kore NP-katoa. huaina e taua raruraru e NP-waenganui raruraru. Ko te raruraru isomorphism graph, te raruraru logarithm motuhake me te raruraru factorization tau tōpū he tauira o ngā raruraru whakapono ki te kia NP-waenganui. Ko ratou etahi o nga raruraru NP rawa torutoru e kore e mohiotia ki te kia i roto i te P ranei ki te kia NP-katoa. Pātai: He aha e huaina enei raruraru?
Ngā raruraru takawaenga NP