Ағылшыншамен салыстырыңыз: абзацты басыңыз — түпнұсқа терезеде ашылады. Абзац астындағы EN түймесі оны мәтін ішінде көрсетеді.
Мазмұны
Кіріспе
Күрделілік класы. Жеңіл кіріспе
Complexity class
a gentler introduction
Есептеу күрделілігі теориясында, егер де детерминистік емес полиномиалдық уақытта шешілетін кез келген L мәселесі үшін, L-ден H-ға полиномиалдық уақытта айналдыру болса, онда H есептеулік мәселесі NP-қиын деп аталады. Яғни, егер H үшін шешім табуға 1 уақыт бірлігі жұмсалатын болса, онда H-тың шешімін пайдаланып L мәселесін полиномиалдық уақытта шешуге болады. Осының салдары ретінде, бір NP-қиын мәселені шешуге арналған полиномиалдық алгоритм табу, NP күрделілік класындағы барлық мәселелер үшін полиномиалдық алгоритмдерді береді. P≠NP деп есептелетіндіктен, мұндай алгоритмнің болуы ықтимал емес. NP-қиын мәселелерді шешуге полиномиалдық уақыт алгоритмдері жоқ деп күдіктенуде, бірақ бұл әлі дәлелденбеді. NP-қиын мәселенің қарапайым мысалы – қосынды мәселесі. Формальды түрде, егер H NP-қиын болса, онда оны шешу NP-дегі мәселелерді шешуден кем емес қиын. Дегенмен, керісінше дұрыс емес: кейбір мәселелер шешілмейді, сондықтан NP-дегі барлық мәселелерден де қиын, бірақ олар NP-қиын емес (егер P=NP болмаса).
In computational complexity theory, a computational problem H is called NP hard if, for every problem L which can be solved in non deterministic polynomial time, there is a polynomial time reduction from L to H. That is, assuming a solution for H takes 1 unit time, Hs solution can be used to solve L in polynomial time. As a consequence, finding a polynomial time algorithm to solve a single NP hard problem would give polynomial time algorithms for all the problems in the complexity class NP. As it is suspected that P≠NP, it is unlikely that such an algorithm exists. It is suspected that there are no polynomial time algorithms for NP hard problems, but that has not been proven. A simple example of an NP hard problem is the subset sum problem. Informally, if H is NP hard, then it is at least as difficult to solve as the problems in NP. However, the opposite direction is not true: some problems are undecidable, and therefore even more difficult to solve than all problems in NP, but they are provably not NP hard (unless P=NP).
Анықтама
H шешімдік есеп NP-қиын деп аталады, егер NP класындағы кез келген L есебі үшін L-ден H-ға полиномдық уақытта көптеген бірге келтірулер бар болса.
A decision problem H is NP hard when for every problem L in NP, there is a polynomial time many one reduction from L to H.
Мысалдар
Барлық NP толық проблемалары да NP қиын (NP толық проблемаларының тізімін қараңыз). Мысалы, салмақты графтың барлық түйіндері арқылы ең төмен құнмен өтетін циклдік маршрутты табудың оптимизациялық мәселесі, көбінесе саяхатшы сатушысының мәселесі деп аталады, NP қиын. Көшірім жиынтығының мәселесі тағы бір мысал: егер бүтін сандар жиынтығы берілсе, олардың бос емес кез келген кіші жиынның қосындысы нөлге тең бола ма? Бұл шешім қабылдау мәселесі және сәйкес келіп NP толық. NP қиын, бірақ NP толық емес шешім қабылдау мәселелері де бар, мысалы тоқтату мәселесі. Бұл мәселе мынандай сұрақ қояды: «берілген бағдарлама мен оның кіріс деректері болса, ол мәңгілікке жұмыс істей ме?» Бұл «иә» немесе «жоқ» сұрағы, сондықтан бұл шешім қабылдау мәселесі. Тоқтату мәселесінің NP қиын, бірақ NP толық емес екенін дәлелдеу оңай. Мысалы, Бульдік қанағаттандыру мәселесін тоқтату мәселесіне дейін азайтуға болады, оны барлық шындық мәнін тағайындауға тырысатын және формулаға қанағаттандыратын мәнді тапқанда тоқтайтын, ал әйтпесе шексіз циклге түсетін Тьюринг машинасының сипаттамасына түрлендіру арқылы. Тоқтату мәселесінің NP-де емес екенін көру оңай, өйткені NP-дегі барлық мәселелер шектеулі санда операциялар ішінде шешіледі, бірақ тоқтату мәселесі, жалпы алғанда, шешілмейді. NP толық емес және шешілмейтін NP қиын мәселелер де бар. Мысалы, шындық квантталған Буль формулаларының тілі полиномдық кеңістікте шешіледі, бірақ детерминистік емес полиномдық уақытта емес (NP = PSPACE болмаса).
All NP complete problems are also NP hard (see List of NP complete problems). For example, the optimization problem of finding the least cost cyclic route through all nodes of a weighted graph—commonly known as the travelling salesman problem—is NP hard. The subset sum problem is another example: given a set of integers, does any non empty subset of them add up to zero? That is a decision problem and happens to be NP complete. There are decision problems that are NP hard but not NP complete such as the halting problem. That is the problem which asks "given a program and its input, will it run forever?" That is a yes/no question and so is a decision problem. It is easy to prove that the halting problem is NP hard but not NP complete. For example, the Boolean satisfiability problem can be reduced to the halting problem by transforming it to the description of a Turing machine that tries all truth value assignments and when it finds one that satisfies the formula it halts and otherwise it goes into an infinite loop. It is also easy to see that the halting problem is not in NP since all problems in NP are decidable in a finite number of operations, but the halting problem, in general, is undecidable. There are also NP hard problems that are neither NP complete nor Undecidable. For instance, the language of true quantified Boolean formulas is decidable in polynomial space, but not in non deterministic polynomial time (unless NP = PSPACE).