Кіріспе
Шешім проблемаларын жіктеу үшін қолданылатын күрделілік класы. Есептеу күрделілігі теориясында NP (детерминистік емес полиномиалдық уақыт) — шешім проблемаларын жіктеу үшін қолданылатын күрделілік класы. NP — жауабы «иә» болғанда, детерминистік Тьюринг машинасымен полиномиалдық уақытта тексерілетін дәлелдері бар шешім проблемаларының жиынтығы, немесе детерминистік емес Тьюринг машинасымен полиномиалдық уақытта шешілетін проблемалар жиынтығы. NP — детерминистік емес Тьюринг машинасымен полиномиалдық уақытта шешілетін шешім проблемаларының жиынтығы. NP — детерминистік Тьюринг машинасымен полиномиалдық уақытта тексерілетін шешім проблемаларының жиынтығы. Бірінші анықтама NP аббревиатурасының негізі болып табылады: «детерминистік емес, полиномиалдық уақыт». Бұл екі анықтама эквивалентті, өйткені Тьюринг машинасына негізделген алгоритм екі кезеңнен тұрады: біріншісінде шешім туралы болжам жасалады, ол детерминистік емес жолмен құрылады, ал екінші кезеңде болжам мәселенің шешімі болатынын тексертін детерминистік алгоритм қолданылады. Күрделілік класы P (барлық проблемалар детерминистік түрде полиномиалдық уақытта шешіледі) NP-нің ішінде қамтылғанын көру оңай, себебі егер проблема полиномиалдық уақытта шешілсе, онда шешімін де полиномиалдық уақытта тексеруге болады. Бірақ NP көптеген проблемаларды қамтиды, олардың ең қиындары NP-толық проблемалар деп аталады. Мұндай проблеманы полиномиалдық уақытта шешетін алгоритм кез келген басқа NP проблемасын да полиномиалдық уақытта шеше алады. Ең маңызды «P = NP?» мәселесі, NP-толық және барлық NP проблемаларын шешу үшін полиномиалдық уақыт алгоритмдері бар ма деп сұрайды. Көпшілік бұлай емес деп санайды. NP күрделілік класы co-NP күрделілік класымен байланысты, онда «жоқ» жауабы полиномиалдық уақытта тексеріледі. Бұл күрделілік теориясындағы тағы бір ашық мәселе.
In computational complexity theory, NP (nondeterministic polynomial time) is a complexity class used to classify decision problems. NP is the set of decision problems for which the problem instances, where the answer is "yes", have proofs verifiable in polynomial time by a deterministic Turing machine, or alternatively the set of problems that can be solved in polynomial time by a nondeterministic Turing machine. NP is the set of decision problems solvable in polynomial time by a nondeterministic Turing machine. NP is the set of decision problems verifiable in polynomial time by a deterministic Turing machine. The first definition is the basis for the abbreviation NP; "nondeterministic, polynomial time". These two definitions are equivalent because the algorithm based on the Turing machine consists of two phases, the first of which consists of a guess about the solution, which is generated in a nondeterministic way, while the second phase consists of a deterministic algorithm that verifies whether the guess is a solution to the problem. It is easy to see that the complexity class P (all problems solvable, deterministically, in polynomial time) is contained in NP (problems where solutions can be verified in polynomial time), because if a problem is solvable in polynomial time, then a solution is also verifiable in polynomial time by simply solving the problem. But NP contains many more problems, the hardest of which are called NP complete problems. An algorithm solving such a problem in polynomial time is also able to solve any other NP problem in polynomial time. The most important P versus NP (“P = NP?”) problem, asks whether polynomial time algorithms exist for solving NP complete, and by corollary, all NP problems. It is widely believed that this is not the case. The complexity class NP is related to the complexity class co NP, for which the answer "no" can be verified in polynomial time. Whether or not is another outstanding question in complexity theory.
Өмірбаян
Көптеген компьютерлік ғылым мәселелері NP класында, мысалы, көптеген іздеу және оңтайландыру мәселелерінің шешімдік түрлері сияқты.
Басқа сипаттамалар
Сипаттамалық күрделілік теориясы тұрғысынан, NP экзистенциалды екінші реттік логикамен анықталатын тілдер жиынтығымен дәл сәйкес келеді (Фагин теоремасы). NP өте қарапайым интерактивті дәлелдеу жүйесінің түрі ретінде қарастырылуы мүмкін, онда дәлелдеуші дәлелдеу куәлігін ұсынады, ал тексеруші оны тексеретін детерминистік полиномиалдық уақыт машинасы болып табылады. Ол толық, себебі дұрыс дәлелдеу тізбегі болған жағдайда, ол оны қабылдауға мәжбүр етеді, және ол дұрыс, себебі қабылдауға жарамды дәлелдеу тізбегі болмаса, тексеруші қабылдамайды. Күрделілік теориясының маңызды нәтижесі – NP ықтималдықпен тексерілетін дәлелдемелер арқылы шешілетін мәселелер ретінде сипатталуы мүмкін, онда тексеруші O(log n) кездейсоқ биттерді пайдаланады және дәлелдеу тізбегінің тек тұрақты саны битін тексереді (PCP(log n, 1) класы). Бұған қарағанда, жоғарыда сипатталған NP тексерушісі дәлелдеу тізбегіндегі бірнеше жерді "көру арқылы тексеру" арқылы алмастырылуы мүмкін, ал шектеулі монета лақтырулар саны арқылы дұрыс жауапты жоғары ықтималдылықпен анықтауға болады. Бұл жуықтау алгоритмдерінің қиындығы туралы бірнеше нәтижелерді дәлелдеуге мүмкіндік береді.
P
P-дегі барлық мәселелер, егер мәселенің P класындағы сертификаты берілсе, онда сертификатты назарға алмастан, мәселені полиномиалдық уақытта шешуге болады.
Субграф изоморфизмі
Субграф изоморфизм мәселесі – G графында H графына изоморфты субграф бар-жоғын анықтау.