Ағылшыншамен салыстырыңыз: абзацты басыңыз — түпнұсқа терезеде ашылады. Абзац астындағы EN түймесі оны мәтін ішінде көрсетеді.
Мазмұны
Кіріспе
Күрделілік класы
Complexity class
Есептеу күрделілігі теориясында #P күрделілік класы (кейде "шарпы P" немесе "сан P" немесе "хэш P" деп айтылады) – NP жиынындағы шешім есептерімен байланысты сану есептерінің жиынтығы. Әріптеу ретінде, #P – "f(x) функциясын есептеу" түріндегі функциялық есептер класы, мұнда f – полиномдық уақытта жұмыс істейтін детерминистік емес Тьюринг машинасының қабылдайтын жолдарының саны. Көптеген танымал күрделілік кластарынан айырмашылығы, бұл шешім есептерінің емес, функциялық есептердің класы. Бұл кластың ең қиын, өкілді есептері #P-толық.
In computational complexity theory, the complexity class #P (pronounced "sharp P" or, sometimes "number P" or "hash P") is the set of the counting problems associated with the decision problems in the set NP. More formally, #P is the class of function problems of the form "compute f(x)", where f is the number of accepting paths of a nondeterministic Turing machine running in polynomial time. Unlike most well known complexity classes, it is not a class of decision problems but a class of function problems. The most difficult, representative problems of this class are #P complete.
Қатысушы күрделілік сыныптары
Әрине, #P мәселесі сәйкес келетін NP мәселесінен кем болмауы керек. Егер жауаптарды санау оңай болса, онда жауаптардың бар-жоғын анықтау да оңай болуы керек – жай ғана оларды санап, саны нөлден артық па екенін тексеріңіз. Мұндай мәселелердің кейбіреулері, мысалы, түбір табу, FP класына жата алады, ал қалғандары #P-толық. Тода теоремасының бір салдары – #P оракулы бар полиномиалдық уақыт машинасы (P#P) PH-дағы барлық мәселелерді, яғни бүкіл полиномиалдық иерархияны шеше алады. Шындығында, полиномиалдық уақыт машинасына PH-дағы кез келген мәселені шешу үшін тек бір #P сұрауы жеткілікті. Бұл #P-толық мәселелерді нақты шешудің қаншалықты қиын екенін көрсетеді. Күтпегенінен, кейбір қиын деп саналатын #P мәселелері оңай (мысалы, сызықтық уақытты) P мәселелерімен сәйкес келеді. Бұл туралы толық ақпаратты #P complete бетінен табуға болады. #P класына ең жақын шешімдік мәселелер класы – PP, ол есептеу жолдарының көпшілігінің (жартысынан астамының) қабылдауын сұрайды. Бұл #P мәселесінің ең маңызды битін анықтайды. Ал ⊕P (айтылуы: "Паритет P") шешімдік мәселелер класы #P жауабының ең кем маңызды битін сұрайды.
Clearly, a #P problem must be at least as hard as the corresponding NP problem. If it's easy to count answers, then it must be easy to tell whether there are any answers—just count them and see whether the count is greater than zero. Some of these problems, such as root finding, are easy enough to be in FP, while others are #P complete. One consequence of Toda's theorem is that a polynomial time machine with a #P oracle (P#P) can solve all problems in PH, the entire polynomial hierarchy. In fact, the polynomial time machine only needs to make one #P query to solve any problem in PH. This is an indication of the extreme difficulty of solving #P complete problems exactly. Surprisingly, some #P problems that are believed to be difficult correspond to easy (for example linear time) P problems. For more information on this, see #P complete. The closest decision problem class to #P is PP, which asks whether a majority (more than half) of the computation paths accept. This finds the most significant bit in the #P problem answer. The decision problem class ⊕P (pronounced "Parity P") instead asks for the least significant bit of the #P answer.
Тарих
#P күрделілік класын алғаш рет Лесли Валиант 1979 жылы квадрат матрицаның анықтамасын есептеу туралы мақаласында анықтады, онда ол анықтаманың #P-толық екенін дәлелдеді. Ларри Стокмайер #P проблемасының кез келгені үшін SAT оракулын қолданатын кездейсоқ алгоритмнің бар екенін дәлелдеді, бұл алгоритм берілген мысал үшін жоғары ықтималдықпен мәнді қайтарады. Алгоритмнің жұмыс істеу уақыты және мысалдың ұзындығына қатысты полиномдық, ал алгоритм қалдық хеш леммасына негізделген.
The complexity class #P was first defined by Leslie Valiant in a 1979 article on the computation of the permanent of a square matrix, in which he proved that permanent is #P complete. Larry Stockmeyer has proved that for every #P problem there exists a randomized algorithm using an oracle for SAT, which given an instance of and returns with high probability a number such that The runtime of the algorithm is polynomial in and The algorithm is based on the leftover hash lemma.