Ағылшыншамен салыстырыңыз: абзацты басыңыз — түпнұсқа терезеде ашылады. Абзац астындағы EN түймесі оны мәтін ішінде көрсетеді.
Мазмұны
Кіріспе
Жуықтамалы есептердің қиындық класы
Complexity class of approximable problems
Есептеу күрделілігі теориясында APX класы ("жуықтамалы" деген сөздің аббревиатурасы) – бұл тұрақты (немесе қысқаша, тұрақты факторлы жуықтамалы алгоритмдер) арқылы шектелген жуықтамалы қатынасы бар полиномиалдық уақытқа жуықтамалы алгоритмдерге ие NP оңтайландыру мәселелерінің жиынтығы. Қарапайым тілмен айтқанда, осы кластағы мәселелер үшін оңтайлы жауаптан белгілі бір тұрақты көбейту коэффициенті ішінде жауапты таба алатын тиімді алгоритмдер бар. Егер алгоритм тапқан шешімнің ең көп дегенде оңтайлы шешімнен бірнеше есе нашар екендігі дәлелденсе, онда ол кіріс мөлшері үшін жуықтамалы алгоритм деп аталады. Мұндағы көбейту коэффициенті жуықтамалы қатынас деп аталады. APX класындағы мәселелер үшін жуықтамалы қатынас тұрақты болады. Жуықтамалы қатынас әдетте 1-ден жоғары көрсетіледі. Минимизациялау мәселесінде табылған шешімнің мәні оңтайлы шешімнің мәніне бөлінеді, ал максимизациялау мәселесінде керісінше. Максималдау мәселелері үшін, егер нашар шешімнің мәні кішірек болса, жуықтамалы қатынас кейде 1-ден кем деп көрсетіледі; мұндай жағдайларда, жуықтамалы қатынастың кері шамасы табылған шешімнің мәнінің оңтайлы шешімнің мәніне қатынасын көрсетеді. Егер 1-ден нашаррақ әрбір көбейту коэффициенті үшін мәселені сол фактордың ішінде шешуге мүмкіндік беретін полиномиалдық уақытқа жуықтамалы схема (PTAS) болса, онда мәселеде PTAS бар деп айтылады. P = NP болмаса, APX класында, бірақ PTAS-қа ие емес мәселелер бар, сондықтан PTAS-қа ие мәселелер класы APX класының ішінде қатаң түрде орналасқан. Мұндай мәселелердің бірі – қоқыс жәшіктерін толтыру мәселесі.
In computational complexity theory, the class APX (an abbreviation of "approximable") is the set of NP optimization problems that allow polynomial time approximation algorithms with approximation ratio bounded by a constant (or constant factor approximation algorithms for short). In simple terms, problems in this class have efficient algorithms that can find an answer within some fixed multiplicative factor of the optimal answer. An approximation algorithm is called an approximation algorithm for input size if it can be proven that the solution that the algorithm finds is at most a multiplicative factor of times worse than the optimal solution. Here, is called the approximation ratio. Problems in APX are those with algorithms for which the approximation ratio is a constant The approximation ratio is conventionally stated greater than 1. In the case of minimization problems, is the found solution's score divided by the optimum solution's score, while for maximization problems the reverse is the case. For maximization problems, where an inferior solution has a smaller score, is sometimes stated as less than 1; in such cases, the reciprocal of is the ratio of the score of the found solution to the score of the optimum solution. A problem is said to have a polynomial time approximation scheme (PTAS) if for every multiplicative factor of the optimum worse than 1 there is a polynomial time algorithm to solve the problem to within that factor. Unless P = NP there exist problems that are in APX but without a PTAS, so the class of problems with a PTAS is strictly contained in APX. One such problem is the bin packing problem.
APX-қаттылығы және APX-толықтығы
Мәселе, егер APX класындағы кез келген мәселені сол мәселеге PTAS азайту арқылы келтіруге болса, APX-қа қиын деп аталады, ал егер мәселе APX-қа қиын болса және APX класында болса, APX-қа толық деп аталады. P ≠ NP ⇒ PTAS ≠ APX салдарынан, егер P ≠ NP деп есептесек, ешқандай APX-қа қиын мәселенің PTAS схемасы болмайды. Іс жүзінде, APX толықтығын көрсету үшін бір мәселені екіншісіне азайтуды басқа азайту схемаларын қолдану арқылы жиі жасайды, мысалы L азайтулары, олар PTAS азайтуларын білдіреді.
A problem is said to be APX hard if there is a PTAS reduction from every problem in APX to that problem, and to be APX complete if the problem is APX hard and also in APX. As a consequence of P ≠ NP ⇒ PTAS ≠ APX, if P ≠ NP is assumed, no APX hard problem has a PTAS. In practice, reducing one problem to another to demonstrate APX completeness is often done using other reduction schemes, such as L reductions, which imply PTAS reductions.
PTAS
PTAS (полиномиалдық уақытқа жуықтату схемасы) – кіріс мөлшеріне полиномиалдық уақытта, 1-ден басқа кез келген тұрақты факторға дейін жуықтауға болатын, бірақ полиномиал осындай факторға тәуелді болатын мәселелер жиынтығы. Бұл класс APX-тің ішкі жиыны болып табылады.
PTAS (polynomial time approximation scheme) consists of problems that can be approximated to within any constant factor besides 1 in time that is polynomial to the input size, but the polynomial depends on such factor. This class is a subset of APX.
APX-орталық
Егер P = NP болмаса, APX класында PTAS-қа да, APX-толыққа да жатпайтын мәселелер бар. Мұндай мәселелерді PTAS мәселелері мен APX-толық мәселелері арасындағы қиындық деңгейі деп санауға болады және оларды APX аралық деп атауға болады. Қоқыс жәшігін толтыру мәселесі APX аралық мәселе деп есептеледі. Белгілі PTAS болмауына қарамастан, қоқыс жәшігін толтыру мәселесі үшін бірнеше "асимптотикалық PTAS" алгоритмі бар, олар ең жақсы шешім үлкен болған кезде PTAS сияқты жұмыс істейді, сондықтан интуитивті түрде APX қиын мәселелерге қарағанда оңайырақ болуы мүмкін. Тағы бір мүмкін APX аралық мәселе – ең аз жиекті бояу.
Unless P = NP, there exist problems in APX that are neither in PTAS nor APX complete. Such problems can be thought of as having a hardness between PTAS problems and APX complete problems, and may be called APX intermediate. The bin packing problem is thought to be APX intermediate. Despite not having a known PTAS, the bin packing problem has several "asymptotic PTAS" algorithms, which behave like a PTAS when the optimum solution is large, so intuitively it may be easier than problems that are APX hard. One other example of a potentially APX intermediate problem is min edge coloring.
f ((n) - APX
Сондай-ақ, APX күрделілік сыныптарының отбасын анықтауға болады, онда APX шама қатынасымен полиномиалдық уақытта жуықтау алгоритмі бар мәселелерді қамтиды. APX-ке толық сыныптарды да ұқсас түрде анықтауға болады; мұндай сыныптардың кейбіреулерінде белгілі оңтайландыру мәселелері бар. Log APX толықтығы мен poly APX толықтығы PTAS азайтулары емес, AP азайтулары арқылы анықталады; себебі PTAS азайтулары Log APX және Poly APX-ке жататындықты сақтау үшін жеткіліксіз, тіпті олар APX үшін жеткілікті болса да. Кіріс мөлшеріне логарифмдік фактормен жуықтауға болатын ең қиын мәселелерден тұратын Log APX толық, шексіз дәрежелі ең кіші үстем жиынтықты қамтиды. Poly APX толық, кіріс мөлшеріне полиномдық фактормен жуықтауға болатын ең қиын мәселелерден тұрады, және жалпы жағдайда ең үлкен тәуелсіз жиынтықты қамтиды. Сондай-ақ, exp APX толық проблемалары бар, онда жуықтау қатынасы кіріс мөлшеріне қатысты экспоненциалды болады. Мұндай жағдай мәселенің мысалындағы сандардың мәніне жуықтау тәуелді болғанда туындауы мүмкін; бұл сандар олардың мәніне қатысты логарифмдік кеңістікте көрсетілуі мүмкін, соның салдарынан экспоненциалдық фактор пайда болады.
One can also define a family of complexity classes APX, where APX contains problems with a polynomial time approximation algorithm with a approximation ratio. One can analogously define APX complete classes; some such classes contain well known optimization problems. Log APX completeness and poly APX completeness are defined in terms of AP reductions rather than PTAS reductions; this is because PTAS reductions are not strong enough to preserve membership in Log APX and Poly APX, even though they suffice for APX. Log APX complete, consisting of the hardest problems that can be approximated efficiently to within a factor logarithmic in the input size, includes min dominating set when degree is unbounded. Poly APX complete, consisting of the hardest problems that can be approximated efficiently to within a factor polynomial in the input size, includes max independent set in the general case. There also exist problems that are exp APX complete, where the approximation ratio is exponential in the input size. This may occur when the approximation is dependent on the value of numbers within the problem instance; these numbers may be expressed in space logarithmic in their value, hence the exponential factor.