Бір мәселені шешу үшін екінші мәселені пайдалану әдісі
Polynomial-time reduction
Полиномиалдық уақыт азайтуы: бір мәселені екіншісі арқылы шешу әдісі. Егер екінші мәселені шешетін алгоритм болса, біріншісі де шешіледі. Теориялық мақала.
Ағылшыншамен салыстырыңыз: абзацты басыңыз — түпнұсқа терезеде ашылады. Абзац астындағы EN түймесі оны мәтін ішінде көрсетеді.
Мазмұны
Кіріспе
Бір мәселені екіншісі арқылы шешу әдісі
Method for solving one problem using another
Есептеу күрделілігі теориясында полиномиалдық уақыт азайту – бір мәселені екіншісін пайдаланып шешу әдісі. Егер екінші мәселені шешетін гипотетикалық процедура болса, онда бірінші мәселені екінші мәселенің кіріс деректеріне түрлендіру (азайту) және осы процедураны бір немесе бірнеше рет шақыру арқылы шешуге болады. Бірінші мәселені екіншісіне түрлендіруге кеткен уақыт пен процедураны шақыру саны полиномиалды болса, онда бірінші мәселе полиномиалдық уақыт бойынша екінші мәселеге айналдырылады. Полиномиалдық уақыт азайту бірінші мәселенің екіншісінен қиын емес екенін көрсетеді, себебі егер екінші мәселе үшін тиімді алгоритм болса, онда бірінші мәселе үшін де тиімді алгоритм болады. Кері тұжырым бойынша, егер бірінші мәселе үшін тиімді алгоритм болмаса, онда екінші мәселе үшін де жоқ. Ең жалпы азайтулар – Тьюринг азайтулары, ал ең шектеулілері – көптен біреу азайтулары, ал шындық кестесі азайтулары олардың арасындағы орынды алып жатады.
In computational complexity theory, a polynomial time reduction is a method for solving one problem using another. One shows that if a hypothetical subroutine solving the second problem exists, then the first problem can be solved by transforming or reducing it to inputs for the second problem and calling the subroutine one or more times. If both the time required to transform the first problem to the second, and the number of times the subroutine is called is polynomial, then the first problem is polynomial time reducible to the second. A polynomial time reduction proves that the first problem is no more difficult than the second one, because whenever an efficient algorithm exists for the second problem, one exists for the first problem as well. By contraposition, if no efficient algorithm exists for the first problem, none exists for the second either. The most general reductions are the Turing reductions and the most restrictive are the many one reductions with truth table reductions occupying the space in between.
Көп-бірлік азайтулар
Полиномиалдық уақыттағы көп-бір редукция – А проблемасынан В проблемасына (әдетте екеуі де шешім проблемалары болуы керек) – А проблемасының кіріс деректерін В проблемасының кірісіне полиномиалдық уақытта түрлендіретін алгоритм, мұнда түрлендірілген проблеманың нәтижесі бастапқы проблеманың нәтижесімен сәйкес келеді. А проблемасының x мысалы осы түрлендіруді қолдану арқылы В проблемасының y мысалын алуға болады, содан кейін y-ды В проблемасы үшін алгоритмге кіріс ретінде беріп, оның нәтижесін қайтару арқылы шешіледі. Полиномиалдық уақыттағы көп-бір редукциялар Ричард Карптың атымен аталған полиномиалдық түрлендірулер немесе Карп редукциялары деп те аталады. Мұндай редукция "≤" немесе "≼" арқылы белгіленеді.
A polynomial time many one reduction from a problem A to a problem B (both of which are usually required to be decision problems) is a polynomial time algorithm for transforming inputs to problem A into inputs to problem B, such that the transformed problem has the same output as the original problem. An instance x of problem A can be solved by applying this transformation to produce an instance y of problem B, giving y as the input to an algorithm for problem B, and returning its output. Polynomial time many one reductions may also be known as polynomial transformations or Karp reductions, named after Richard Karp. A reduction of this type is denoted by or .
Тьюрингтік қысқартулар
Полиномиялық уақыттағы Тьюринг редукциясы – А проблемасын В проблемасының субрутинасына полиномиялық санда қоңырау шалу арқылы және сол субрутиналарға қоңырау шалудан тыс полиномиялық уақытты пайдалану арқылы шешетін алгоритм. Полиномиялық уақыт Тьюринг редукциялары Стивен Кук есімімен Кук редукциялары деп те аталады. Мұндай редукцияны полиномиялық уақытты көп-бірге редукция деп белгілеуге болады. Бұл редукциялар басқа күрделік сыныптары үшін, соның ішінде PSPACE-толық тілдері мен EXPTIME-толық тілдері үшін толық проблемаларды анықтау үшін қолданылған. P класындағы (полиномиялық уақыт шешім проблемаларының класы) әрбір шешім мәселесі, тривиалды емес әрбір басқа шешім мәселесіне (тривиалды емес дегеніміз, әрбір кіріс бірдей шығыс емес) полиномиялық уақытты көп-бірге редукция арқылы келтірілуі мүмкін. А проблемасының бір мысалын В-ға түрлендіру үшін, А-ны полиномиялық уақытта шешіп, содан кейін шешімді әртүрлі жауаптары бар В проблемасының екі мысалының біреуін таңдау үшін пайдаланыңыз. Сондықтан, P ішіндегі L, NL, NC және P сияқты күрделік сыныптары үшін толық тілдерді анықтау үшін полиномиялық уақыт редукцияларын қолдануға болмайды: егер олар осылай қолданылса, P-дегі әрбір тривиалды емес мәселе толық болар еді. Оның орнына, логикалық кеңістік редукциясы немесе NC редукциясы сияқты нашар редукциялар осы сыныптар үшін толық проблемалардың сыныптарын анықтау үшін қолданылады, мысалы, P-толық проблемалары.
A polynomial time Turing reduction from a problem A to a problem B is an algorithm that solves problem A using a polynomial number of calls to a subroutine for problem B, and polynomial time outside of those subroutine calls. Polynomial time Turing reductions are also known as Cook reductions, named after Stephen Cook. A reduction of this type may be denoted by the expression Polynomial time many one reductions have been used to define complete problems for other complexity classes, including the PSPACE complete languages and EXPTIME complete languages. Every decision problem in P (the class of polynomial time decision problems) may be reduced to every other nontrivial decision problem (where nontrivial means that not every input has the same output), by a polynomial time many one reduction. To transform an instance of problem A to B, solve A in polynomial time, and then use the solution to choose one of two instances of problem B with different answers. Therefore, for complexity classes within P such as L, NL, NC, and P itself, polynomial time reductions cannot be used to define complete languages: if they were used in this way, every nontrivial problem in P would be complete. Instead, weaker reductions such as log space reductions or NC reductions are used for defining classes of complete problems for these classes, such as the P complete problems.
Күрделілік сыныптарын анықтау
NP, PSPACE және EXPTIME күрделілік сыныптарының анықтамаларында қысқартулар қолданылмайды: қысқартулар осы сыныптар үшін толық тілдерді анықтағанда ғана зерттеледі. Дегенмен, кейбір жағдайларда күрделілік класы қысқарту арқылы анықталуы мүмкін. Егер C кез келген шешім есеп болса, онда C күрделілік класын A тілдерінен тұратын ретінде анықтауға болады, онда C автоматты түрде C үшін толық болады, бірақ C-де басқа да толық есептер болуы мүмкін. Мұның мысалы – нақты сандардың экзистенциалдық теориясынан анықталған күрделілік класы, ол NP-ге қиын және PSPACE-де жататындығы белгілі, бірақ NP, PSPACE немесе полиномдық иерархиядағы кез келген тіл үшін толық емес. Бұл – нақты сандардың экзистенциалдық теориясына полиномдық уақытта көптеген бір-бірге қысқартуларға ие проблемалардың жиынтығы; оның басқа да бірнеше толық есептері бар, мысалы, бағытталмаған графтың тікбұрышты қиылысу санын анықтау. класындағы әрбір есеп PSPACE-ге жататын қасиетке ие болады, ал әрбір толық есеп NP-ге қиын болады. Сол сияқты, GI күрделілік класы граф изоморфизмі есебіне дейін қысқартуға болатын есептерден тұрады. Граф изоморфизмі NP және co AM-ге жататындығы белгілі болғандықтан, осы кластағы әрбір есеп үшін де осы айтуға болады. Есеп осы сынып үшін толық болса, онда ол GI толық болады; граф изоморфизмінің өзі GI толық, сондай-ақ басқа да бірнеше байланысты есептер де GI толық.
The definitions of the complexity classes NP, PSPACE, and EXPTIME do not involve reductions: reductions come into their study only in the definition of complete languages for these classes. However, in some cases a complexity class may be defined by reductions. If C is any decision problem, then one can define a complexity class C consisting of the languages A for which In this case, C will automatically be complete for C, but C may have other complete problems as well. An example of this is the complexity class defined from the existential theory of the reals, a computational problem that is known to be NP hard and in PSPACE, but is not known to be complete for NP, PSPACE, or any language in the polynomial hierarchy. is the set of problems having a polynomial time many one reduction to the existential theory of the reals; it has several other complete problems such as determining the rectilinear crossing number of an undirected graph. Each problem in inherits the property of belonging to PSPACE, and each complete problem is NP hard. Similarly, the complexity class GI consists of the problems that can be reduced to the graph isomorphism problem. Since graph isomorphism is known to belong both to NP and co AM, the same is true for every problem in this class. A problem is GI complete if it is complete for this class; the graph isomorphism problem itself is GI complete, as are several other related problems.