Реоптимизация обобщенных проблем о выполнимости с аппроксимационно-устойчивыми предикатами
Якщо k=O(logn) і предикат P спадково апроксимаційно-стійкий для реоптимізації проблеми Max-EkCSP-P, при вставці нового істинісного значення в предикат і деякого обмеження існує поліноміальний наближений алгоритм з відношенням апроксимації, яке є пороговим. If k=O(logn) and a predicate Р is approxim...
Saved in:
| Published in: | Кибернетика и системный анализ |
|---|---|
| Date: | 2012 |
| Main Authors: | , |
| Format: | Article |
| Language: | Russian |
| Published: |
Інститут кібернетики ім. В.М. Глушкова НАН України
2012
|
| Subjects: | |
| Online Access: | https://nasplib.isofts.kiev.ua/handle/123456789/84019 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| Journal Title: | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| Cite this: | Реоптимизация обобщенных проблем о выполнимости с аппроксимационно-устойчивыми предикатами / В.А. Михайлюк, И.В. Сергиенко // Кибернетика и системный анализ. — 2012. — Т. 48, № 1. — С. 89-104. — Бібліогр.: 23 назв. — рос. |
Institution
Digital Library of Periodicals of National Academy of Sciences of Ukraine| _version_ | 1859624305013293056 |
|---|---|
| author | Михайлюк, В.А. Сергиенко, И.В. |
| author_facet | Михайлюк, В.А. Сергиенко, И.В. |
| citation_txt | Реоптимизация обобщенных проблем о выполнимости с аппроксимационно-устойчивыми предикатами / В.А. Михайлюк, И.В. Сергиенко // Кибернетика и системный анализ. — 2012. — Т. 48, № 1. — С. 89-104. — Бібліогр.: 23 назв. — рос. |
| collection | DSpace DC |
| container_title | Кибернетика и системный анализ |
| description | Якщо k=O(logn) і предикат P спадково апроксимаційно-стійкий для реоптимізації проблеми Max-EkCSP-P, при вставці нового істинісного значення в предикат і деякого обмеження існує поліноміальний наближений алгоритм з відношенням апроксимації, яке є пороговим.
If k=O(logn) and a predicate Р is approximation resistant for the reoptimization of problem Max-EkCSP-P under insertion of a truth-value in the predicate and some constraint, then there exists a polynomial algorithm with the approximation ratio that is threshold
|
| first_indexed | 2025-11-29T10:20:56Z |
| format | Article |
| fulltext |
Â.À. ÌÈÕÀÉËÞÊ, È.Â. ÑÅÐÃÈÅÍÊÎ
ÓÄÊ 519.854 ÐÅÎÏÒÈÌÈÇÀÖÈß ÎÁÎÁÙÅÍÍÛÕ ÏÐÎÁËÅÌ
Î ÂÛÏÎËÍÈÌÎÑÒÈ Ñ ÀÏÏÐÎÊÑÈÌÀÖÈÎÍÍÎ-
ÓÑÒÎÉ×ÈÂÛÌÈ ÏÐÅÄÈÊÀÒÀÌÈ
Êëþ÷åâûå ñëîâà: ðåîïòèìèçàöèÿ, C-ïðèáëèæåííûé àëãîðèòì, äèñêðåòíûé
Ôóðüå-àíàëèç, PCP-òåîðåìà, àïïðîêñèìàöèîííî-óñòîé÷èâûå ïðåäèêàòû.
ÂÂÅÄÅÍÈÅ
Îáîáùåííûå ïðîáëåìû î âûïîëíèìîñòè èëè CSP-ïðîáëåìû (Constraint
Satisfaction Problems) ÿâëÿþòñÿ îáîáùåíèÿìè ìíîãèõ çàäà÷ äèñêðåòíîé îïòè-
ìèçàöèè.  òàêèõ ïðîáëåìàõ îãðàíè÷åíèÿ çàäàþòñÿ k-ìåñòíûì ïðåäèêàòîì P.
Òàê, ïðîáëåìà Max CSP P� � çàêëþ÷àåòñÿ â ñëåäóþùåì: íàéòè òàêîå ïðèïèñû-
âàíèå çíà÷åíèé èñòèííîñòè ïåðåìåííûì, ïðè êîòîðîì ÷èñëî âûïîëíåííûõ
îãðàíè÷åíèé ìàêñèìàëüíî. Ìíîãèå îïòèìèçàöèîííûå ïðîáëåìû ÿâëÿþòñÿ
NP-òðóäíûìè, à çíà÷èò, ðåøèòü èõ òî÷íî çà ïðèåìëåìîå âðåìÿ âðÿä ëè ïðåä-
ñòàâëÿåòñÿ âîçìîæíûì. Çäåñü ðàññìàòðèâàþòñÿ ýôôåêòèâíûå ïðèáëèæåííûå
àëãîðèòìû äëÿ ðåøåíèÿ òàêèõ çàäà÷. Îòíîñèòåëüíî ìàêñèìèçàöèîííîé ïðîáëå-
ìû ñ÷èòàþò, ÷òî àëãîðèòì ÿâëÿåòñÿ C-ïðèáëèæåííûì, åñëè îí äëÿ ïðîèçâîëü-
íîãî ýêçåìïëÿðà äàåò ðåøåíèå ñî çíà÷åíèåì öåëåâîé ôóíêöèè, íå ìåíüøèì
C �OPT, ãäå OPT — ãëîáàëüíûé îïòèìóì, C — îòíîøåíèå àïïðîêñèìàöèè.
Ïîäîáíîå îïðåäåëåíèå ìîæíî äàòü äëÿ ìèíèìèçàöèîííûõ ïðîáëåì.
Ôóíäàìåíòàëüíûé âîïðîñ äëÿ çàäàííîé NP-òðóäíîé ïðîáëåìû çàëþ÷àåòñÿ
â ñëåäóþùåì: îïðåäåëèòü, äëÿ êàêèõ çíà÷åíèé C ìîæíî ïîëàãàòüñÿ íà ýôôåêòèâ-
íûé (ïîëèíîìèàëüíûé) C-ïðèáëèæåííûé àëãîðèòì? Ýòî áîëüøàÿ èññëåäîâàòåëü-
ñêàÿ îáëàñòü, îõâàòûâàþùàÿ òåîðåòè÷åñêóþ èíôîðìàòèêó ñî ñâîèìè ïîçèòèâíû-
ìè è íåãàòèâíûìè ðåçóëüòàòàìè.
Ïîíÿòèå ðåîïòèìèçàöèè [1–7] ñîñòîèò â ñëåäóþùåì. Ïóñòü Q — íåêîòîðàÿ
NP-òðóäíàÿ (âîçìîæíî, NP-ïîëíàÿ) ïðîáëåìà, I — íà÷àëüíûé ýêçåìïëÿð ïðî-
áëåìû Q, îïòèìàëüíîå ðåøåíèå êîòîðîãî èçâåñòíî. Ïðåäëàãàåòñÿ íîâûé ýêçåì-
ïëÿð I � çàäà÷è Q ñ íåêîòîðûìè «íåçíà÷èòåëüíûìè» èçìåíåíèÿìè ýêçåìïëÿðà I .
Âîçíèêàåò âîïðîñ: êàê ìîæíî ýôôåêòèâíî èñïîëüçîâàòü çíàíèÿ îá îïòèìàëüíîì
ðåøåíèè I äëÿ âû÷èñëåíèÿ òî÷íîãî èëè ïðèáëèæåííîãî ðåøåíèÿ ýêçåìïëÿðà I �?
Ñóòü ðåîïòèìèçàöèè ïðè èñïîëüçîâàíèè ïðèáëèæåííûõ ìåòîäîâ — ïðèìåíåíèå
çíàíèé î ðåøåíèè íà÷àëüíîãî ýêçåìïëÿðà I ñ öåëüþ ëèáî äîñòèæåíèÿ ëó÷øåãî
êà÷åñòâà ïðèáëèæåíèÿ (àïïðîêñèìàöèîííîãî îòíîøåíèÿ) I �, ëèáî ñîçäàíèÿ áî-
ëåå ýôôåêòèâíîãî (ïî âðåìåíè) àëãîðèòìà îïðåäåëåíèÿ îïòèìàëüíîãî èëè áëèç-
êîãî ê íåìó ðåøåíèÿ I �, ëèáî âûïîëíåíèÿ îáîèõ óñëîâèé.
Ñ÷èòàþò, ÷òî äëÿ ïðîáëåìû Q óñòàíîâëåíà âåðõíÿÿ îöåíêà îòíîøåíèÿ àï-
ïðîêñèìàöèè C, åñëè ñóùåñòâóåò ïîëèíîìèàëüíûé C-ïðèáëèæåííûé àëãîðèòì äëÿ
ðåøåíèÿ Q. Äëÿ ýòîé ïðîáëåìû óñòàíîâëåíà íèæíÿÿ îöåíêà îòíîøåíèÿ àïïðîêñè-
ìàöèè c, åñëè äëÿ ïðîèçâîëüíîãî �� 0 íå ñóùåñòâóåò ïîëèíîìèàëüíîãî ïðèáëè-
ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2012, ¹ 1 89
© Â.À. Ìèõàéëþê, È.Â. Ñåðãèåíêî, 2012
æåííîãî àëãîðèòìà äëÿ Q, íà êîòîðîì äîñòèãàåòñÿ îòíîøåíèå àïïðîêñèìàöèè c� �.
Åñëè C c� , òî äëÿ ïðîáëåìû Q óñòàíîâëåí ïîðîã îòíîøåíèÿ àïïðîêñèìàöèè.
Äëÿ íåêîòîðûõ ïðîáëåì óäàëîñü óñòàíîâèòü ïîðîã îòíîøåíèÿ àïïðîêñèìà-
öèè, íàïðèìåð äëÿ Max E SAT� �3 — ïîðîã
7
8
, äëÿ Max E Lin� � �3 2 — ïîðîã
1
2
[8],
äëÿ çàäà÷è î ïîêðûòèè ìíîæåñòâàìè — ïîðîã ln n [11].
Ïðîáëåìà óñòàíîâëåíèÿ íèæíèõ îöåíîê îòíîøåíèÿ àïïðîêñèìàöèè (êàê è
ëþáàÿ ïðîáëåìà ïîëó÷åíèÿ íèæíèõ îöåíîê ñëîæíîñòè) ÿâëÿåòñÿ äîâîëüíî òðóä-
íîé. Äëÿ òàêîé ïðîáëåìû ñóùåñòâóåò òåðìèí «íåàïïðîêñèìèðóåìîñòü»
(inapproximability), ò.å. òðóäíîñòü àïïðîêñèìàöèè (hardness of approximation).
Áîëüøîå âëèÿíèå íà ðàçâèòèå ìåòîäîâ ïîëó÷åíèÿ íèæíèõ îöåíîê îêàçàëè èçâåñò-
íàÿ PCP-òåîðåìà [12] è äèñêðåòíûé àíàëèç Ôóðüå äëÿ òåñòèðîâàíèÿ ñâîéñòâ
ïðîáëåì (property testing) [13, 14].
Èçâåñòíû ñëåäóþùèå ðåçóëüòàòû, ïîëó÷åííûå ïðè ðåîïòèìèçàöèè äèñêðåò-
íûõ çàäà÷ îïòèìèçàöèè. Ïðè âñòàâêå ýëåìåíòàðíîé äèçúþíêöèè â ýêçåìïëÿð
ïðîáëåìû ðåîïòèìèçàöèÿ çàäà÷è Max Weighted Sat (âçâåøåííàÿ çàäà÷à î âûïîë-
íèìîñòè íà ìàêñèìóì) àïïðîêñèìèðóåìà ñ îòíîøåíèåì 0.81, õîòÿ çàäà÷à Max
Weighted Sat àïïðîêñèìèðóåìà ñ îòíîøåíèåì 0.77 [7]. Ïðè âñòàâêå âåðøèíû
â ãðàô ðåîïòèìèçàöèÿ Min Vertex Cover (ìèíèìàëüíîå âåðøèííîå ïîêðûòèå ãðà-
ôà) àïïðîêñèìèðóåìà ñ îòíîøåíèåì 1.5, Min Vertex Cover — ñ îòíîøåíèåì 2 [7].
Ïðè âñòàâêå âåðøèíû (òåðìèíàëüíîé èëè íåòåðìèíàëüíîé) ðåîïòèìèçàöèÿ Min
Steiner Tree (ìèíèìàëüíîå äåðåâî Øòåéíåðà) àïïðîêñèìèðóåìà ñ îòíîøåíèåì 1.5,
à çàäà÷à Min Steiner Tree àïïðîêñèìèðóåìà ñ îòíîøåíèåì1 3 2 155� �ln( ) / . [4].
Ïðè âñòàâêå èëè óäàëåíèè ýëåìåíòà èç ìíîæåñòâà çàäà÷à î ïîêðûòèè ìíî-
æåñòâàìè àïïðîêñèìèðóåìà ñ îòíîøåíèåì (
ln
)2
1
1
�
�m
, ãäå m — ÷èñëî ýëå-
ìåíòîâ ìíîæåñòâà. Ïîäîáíûé ðåçóëüòàò èìååò ìåñòî ïðè âñòàâêå èëè óäàëåíèè ïðî-
èçâîëüíîãî ÷èñëà 1 p m ýëåìåíòîâ èç ìíîæåñòâà [23]. Ñëåäóåò îòìåòèòü öèêë ðà-
áîò ïî ðåîïòèìèçàöèè çàäà÷è î êîììèâîÿæåðå (TSP — Travelling Salesman Problem)
[1–3, 5]. Íàïðèìåð, çàäà÷à Minimum Metric TSP (Min TSP — çàäà÷à î êîììèâîÿæåðå
íà ìèíèìóì ñ ìåòðè÷åñêèìè ðàññòîÿíèÿìè) àïïðîêñèìèðóåìà ñ îòíîøåíèåì 1.5, åå
ðåîïòèìèçàöèÿ ïðè âñòàâêå íîâîãî óçëà — ñ îòíîøåíèåì 1.34, ðåîïòèìèçàöèÿ ýòîé
çàäà÷è ïðè èçìåíåíèè ðàññòîÿíèé àïïðîêñèìèðóåìà ñ îòíîøåíèåì 1.4 [7]. Äëÿ îáùåé
çàäà÷è î êîììèâîÿæåðå (Min TSP) íåèçâåñòíû îöåíêè àïïðîêñèìàöèè êàê íåïîñðåä-
ñòâåííî äëÿ íåå, òàê è äëÿ ðàçëè÷íûõ âåðñèé ðåîïòèìèçàöèè.
Èçâåñòíî, ÷òî ïðîáëåìà Max CSP P� � ÿâëÿåòñÿ NP-òðóäíîé äëÿ ïðåäèêàòîâ
P, êîòîðûå çàâèñÿò íå ìåíåå ÷åì îò äâóõ ïåðåìåííûõ [16]. Ïðåäñòàâëÿåò èíòåðåñ
íàõîæäåíèå ýôôåêòèâíîãî àïïðîêñèìàöèîííîãî àëãîðèòìà äëÿ ýòîé ïðîáëåìû.
Òðèâèàëüíûé àëãîðèòì — ïðèïèñàòü ïåðåìåííûì ñëó÷àéíûå çíà÷åíèÿ.  [8–10]
Õàñòàä ïîêàçàë, ÷òî, èñïîëüçóÿ ýòè ñëó÷àéíûå ïðèïèñûâàíèÿ, ìîæíî ïîëó÷èòü
àïïðîêñèìàöèîííûé îïòèìàëüíûé àëãîðèòì äëÿ Max CSP P� � (ñ äîñòèæåíèåì
ïîðîãà àïïðîêñèìàöèîííîãî îòíîøåíèÿ) ïðè íåêîòîðûõ ïðåäèêàòàõ P. Òàêèå
ïðåäèêàòû íàçûâàþò àïïðîêñèìàöèîííî-óñòîé÷èâûìè (approximation resistant).
Îñíîâíîé ðåçóëüòàò íàñòîÿùåé ñòàòüè: ïîëó÷åí ïîëèíîìèàëüíûé àëãîðèòì
ñ íåêîòîðûì îòíîøåíèåì àïïðîêñèìàöèè äëÿ ðåîïòèìèçàöèè ïðîáëåìû
Max CSP P� � ïðè âñòàâêå íåêîòîðîãî îãðàíè÷åíèÿ. Ïîêàçàíî, ÷òî ýòî îòíîøå-
íèå ÿâëÿåòñÿ ïîðîãîâûì, åñëè ïðåäèêàò P ïðèíàäëåæèò êëàññó àïïðîêñèìàöèîí-
íî-óñòîé÷èâûõ ïðåäèêàòîâ. Äîêàçàíà òåîðåìà.
Òåîðåìà 1. Åñëè k O n� ( )log è ïðåäèêàò P àïïðîêñèìàöèîííî-óñòîé÷èâûé, òî
äëÿ ïðîáëåìû Ins Max EkCSP P� � � (ðåîïòèìèçàöèÿ Max EkCSP P� � ) ñóùåñòâó-
åò ïîëèíîìèàëüíûé ïðèáëèæåííûé àëãîðèòì ñ îòíîøåíèåì àïïðîêñèìàöèè
q P
d P
( )
( )
�
�
1
2
, ãäå d P Pk( ) | ( )|� � �2 11 — ïîðîãîâîå «ñëó÷àéíîå» îòíîøåíèå àï-
ïðîêñèìàöèè ïðåäèêàòà P. Îòíîøåíèå àïïðîêñèìàöèè q P( ) ÿâëÿåòñÿ ïîðîãîâûì.
90 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2012, ¹ 1
ÏÎÑÒÀÍÎÂÊÀ ÇÀÄÀ×È. ÀÏÏÐÎÊÑÈÌÀÖÈÎÍÍÎ-ÓÑÒÎÉ×ÈÂÛÅ ÏÐÅÄÈÊÀÒÛ
È ÏÐÎÁËÅÌÛ
Ââåäåì íåîáõîäèìûå îáîçíà÷åíèÿ è îïðåäåëåíèÿ [8, 16]. Ïîä ïðåäèêàòîì P
ðàçìåðíîñòè k áóäåì ïîíèìàòü îòîáðàæåíèå P k: , ,{ } { }�
1 1 0 1 . Äëÿ óäîáñòâà
îáîçíà÷åíèé âõîäíûå äàííûå ñî çíà÷åíèåì –1 èíòåðïðåòèðóåì êàê «èñòèíà»,
ñî çíà÷åíèåì 1 — êàê «ëîæü». Åñëè ïðåäèêàò P ïðèíèìàåò âõîäíîå çíà÷åíèå y,
òî P y( ) �1 , èíà÷å P y( ) � 0. Òàêèì îáðàçîì, ìíîæåñòâî çíà÷åíèé, ïðèíèìàå-
ìûõ ïðåäèêàòîì P, îáîçíà÷àåòñÿ P �1 1( ). Ëîãè÷åñêèå AND, OR è XOR îò äâóõ
ïåðåìåííûõ îáîçíà÷èì êàê x y x y� �, è x y
ñîîòâåòñòâåííî. Äëÿ öåëîãî k
îáîçíà÷èì ïðåäèêàòû kOR kAND, è kXOR êàê ëîãè÷åñêîå OR AND, è XOR îò
k ïåðåìåííûõ ñîîòâåòñòâåííî. Åñëè kXOR x xk( , , )1 1� � , òî ( , , )x xk1 � èìååò
íå÷åòíûé ïàðèòåò, èíà÷å — ÷åòíûé ïàðèòåò. Áóëåâóþ ïåðåìåííóþ èëè åå îò-
ðèöàíèå áóäåì ñ÷èòàòü ëèòåðàëîì.
Îïðåäåëåíèå 1. Ïóñòü P k: , ,{ } { }�
1 1 0 1 åñòü ïðåäèêàò. Ýêçåìïëÿð ïðîáëå-
ìû Max CSP P� � ñîñòîèò èç m âçâåøåííûõ îãðàíè÷åíèé, êàæäîå èç êîòîðûõ ïðåä-
ñòàâëÿåò k — êîðòåæ ëèòåðàëîâ ( , , )z zi ik1
� , âçÿòûõ èç ìíîæåñòâà {x xn1, , ,�
x xn1, ,� }. Âñå ïåðåìåííûå â ýòîì êîðòåæå ñ÷èòàþòñÿ ðàçíûìè. Îãðàíè÷åíèå
âûïîëíåíî òîãäà è òîëüêî òîãäà, êîãäà P ïðèíèìàåò ýòîò êîðòåæ. Ðåøåíèå ñîñòî-
èò â ïðèïèñûâàíèè èñòèííîñòíûõ çíà÷åíèé ê ìíîæåñòâó { }x xn1, ,� .  ðåçóëüòà-
òå ðåøåíèÿ èìååì w P z zi
i
m
i ik
�
�
1
1
( , , )� , ãäå wi åñòü (íå îòðèöàòåëüíûé) âåñ i-ãî
îãðàíè÷åíèÿ. Öåëü ïðîáëåìû ñîñòîèò â ìàêñèìèçàöèè ýòîãî çíà÷åíèÿ. Êîãäà P
çàâèñèò íå áîëåå ÷åì îò k ëèòåðàëîâ, Max CSP P� � áóäåì íàçûâàòü
Max kCSP P� � ; åñëè â P òî÷íî k ëèòåðàëîâ, òî áóäåì íàçûâàòü Max EkCSP P� � .
Íàðÿäó ñ ïðîáëåìàìè òèïà Max CSP P� � ðàññìàòðèâàþòñÿ ïðîáëåìû òèïà
CSP P� , öåëü êîòîðûõ ñîñòîèò â íàõîæäåíèè òàêîãî ïðèïèñûâàíèÿ, êîãäà âñå îãðà-
íè÷åíèÿ âûïîëíåíû (àíàëîãè÷íî îïðåäåëÿþòñÿ ïðîáëåìû kCSP P� è EkCSP P� ).
Îïðåäåëåíèå 2. Äâà k-ìåñòíûõ ïðåäèêàòà P è P�èìåþò îäèíàêîâûé òèï
òîãäà è òîëüêî òîãäà, êîãäà ñóùåñòâóåò ïåðåñòàíîâêà � íà [ ] , ,k k� { }1 � è
a k� �{ }1 1, òàêîå, ÷òî P x x P a x a xk k k( , , ) ( , , )( ) ( )1 1 1� �� � � � äëÿ âñåõ x k� �{ }1 1, .
Åñëè P è P� èìåþò îäèíàêîâûé òèï, òî ýêçåìïëÿð ïðîáëåìû Max CSP P� �
ìîæåò áûòü âûðàæåí êàê ýêçåìïëÿð Max CSP P� � �, ïåðåñòàâëÿÿ êîðòåæè ñîãëàñ-
íî ìàñêå, ò.å. ýòè ïðîáëåìû ýêâèâàëåíòíû.
Îïðåäåëåíèå 3. Ïðîáëåìà Max kCSP P� � , ãäå êàæäîå îãðàíè÷åíèå åñòü
äèçúþíêöèÿ íå áîëåå k ëèòåðàëîâ, ÿâëÿåòñÿ ïðîáëåìîé Max k SAT� � . Åñëè êàæ-
äîå îãðàíè÷åíèå ñîäåðæèò òî÷íî k ëèòåðàëîâ, òî ýòî ÿâëÿåòñÿ ïðîáëåìîé
Max Ek SAT� � .
Îïðåäåëåíèå 4. Ïðîáëåìà Max kCSP P� � , ãäå êàæäîå îãðàíè÷åíèå åñòü
ïðîèçâåäåíèå íå áîëåå k ëèòåðàëîâ, ðàâíîå êîíñòàíòå, ÿâëÿåòñÿ ïðîáëåìîé
Max k LIN� � . Åñëè êàæäîå îãðàíè÷åíèå ñîäåðæèò òî÷íî k ëèòåðàëîâ, òî ýòî
ïðîáëåìà Max Ek LIN� � .
Ïóñòü w Iopt ( ) — çíà÷åíèå îïòèìàëüíîãî ðåøåíèÿ ýêçåìïëÿðà I . Òîãäà èìååò
ìåñòî îïðåäåëåíèå.
Îïðåäåëåíèå 5. Àëãîðèòì A ÿâëÿåòñÿ C-ïðèáëèæåííûì àëãîðèòìîì äëÿ
ìàêñèìèçàöèîííîé ïðîáëåìû, åñëè äëÿ âñåõ ýêçåìïëÿðîâ I ïðîáëåìû èìååì
w A I C w I( , ) ( )� � opt , ãäå w A I( , ) — çíà÷åíèå ðåøåíèÿ àëãîðèòìà A íà âõîäå I .
Ïðè ýòîì ñ÷èòàþò, ÷òî A èìååò àïïðîêñèìàöèîííîå îòíîøåíèå C. Äëÿ âåðîÿò-
íîñòíûõ àëãîðèòìîâ w A I( , ) ÿâëÿåòñÿ îæèäàåìûì çíà÷åíèåì (ìàòåìàòè÷åñêèì
îæèäàíèåì) ñðåäè ñëó÷àéíûõ âûáîðîâ àëãîðèòìà A.
Ñ÷èòàþò, ÷òî ïðåäèêàò P ÿâëÿåòñÿ àïïðîêñèìàöèîííî-óñòîé÷èâûì (êàê è ñî-
îòâåòñòâóþùàÿ ïðîáëåìà Max CSP P� � ), åñëè NP-òðóäíûì íàõîäèòü ðåøåíèå
Max CSP P� � , êîòîðîå çíà÷èòåëüíî ëó÷øå, ÷åì îæèäàåìîå çíà÷åíèå ïðè ñëó-
÷àéíîì ïðèïèñûâàíèè. Ïîñêîëüêó ñëó÷àéíîå ïðèïèñûâàíèå âûïîëíÿåò ïðîèç-
ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2012, ¹ 1 91
âîëüíîå P-îãðàíè÷åíèå ñ âåðîÿòíîñòüþ d P Pk( ) | ( )|� � �2 11 , òî èìååì ñëåäóþùåå
îïðåäåëåíèå.
Îïðåäåëåíèå 6. Ïðåäèêàò P k: , ,{ } { }�
1 1 0 1 íàçûâàåòñÿ àïïðîêñèìàöèîí-
íî-óñòîé÷èâûì, åñëè äëÿ ïðîèçâîëüíîé êîíñòàíòû �� 0 íàéòè ðåøåíèå x ýêçåì-
ïëÿðà I ïðîáëåìû Max CSP P� � òàêîå, ÷òî çíà÷åíèå x, íå ìåíüøåå
( ( ) ) ( )d P w I� � opt , ÿâëÿåòñÿ NP-òðóäíûì.
Îïðåäåëåíèå 7. Ïðîáëåìà Max CSP P� � âñåãäà àïïðîêñèìèðóåìà, åñëè äëÿ
ïðîèçâîëüíîãî �� 0 ñóùåñòâóåò �� � 0 è ýôôåêòèâíûé àëãîðèòì, êîòîðûé èñõîäÿ
èç ýêçåìïëÿðà, ãäå ( ( ) )d P � � — ÷àñòü îãðàíè÷åíèé îäíîâðåìåííî âûïîëíåíà, íà-
õîäèò ïðèïèñûâàíèå, êîòîðîå âûïîëíÿåò ÷àñòü îãðàíè÷åíèé, íå ìåíüøóþ, ÷åì
( ( ) )d P � �� .
Åñëè ïðîáëåìà íå âñåãäà àïïðîêñèìèðóåìà, òî îíà àïïðîêñèìàöèîííî-óñòîé÷èâà.
Îïðåäåëåíèå 8. Ïðåäèêàò P k: , ,{ } { }�
1 1 0 1 íàçûâàåòñÿ íàñëåäñòâåííî àï-
ïðîêñèìàöèîííî-óñòîé÷èâûì, åñëè âñå ïðåäèêàòû P�, êîòîðûå ÿâëÿþòñÿ ñëåä-
ñòâèÿìè P (ò. å. ( ( ) ) ( ( ) )P y P y� � � �1 1 äëÿ âñåõ y), àïïðîêñèìàöèîííî-óñòîé÷èâû.
Òåîðåìà 2 [10]. Ïðîáëåìà Max CSP P� � äîïóñêàåò ïîëèíîìèàëüíî-ïðèáëè-
æåííûé àëãîðèòì ñ îòíîøåíèåì àïïðîêñèìàöèè d P( ) .
Äîêàçàòåëüñòâî. Äîïóñòèì, ÷òî èìååòñÿ ýêçåìïëÿð ñ m îãðàíè÷åíèÿìè.
Ñëó÷àéíîå ïðèïèñûâàíèå âûïîëíÿåò êàæäîå äàííîå îãðàíè÷åíèå ñ âåðîÿòíîñòüþ
d P( ), ò.å. âûïîëíÿåò d P m( ) � îãðàíè÷åíèé â ñðåäíåì. Ïîñêîëüêó îïòèìàëüíîå
ïðèïèñûâàíèå âûïîëíÿåò íå áîëåå m îãðàíè÷åíèé, èìååì ñëó÷àéíûé d P( )-ïðè-
áëèæåííûé àëãîðèòì. Ìåòîäîì óñëîâíûõ âåðîÿòíîñòåé ýòîò ñëó÷àéíûé àëãî-
ðèòì ìîæåò áûòü äåðàíäîìèçèðîâàí [21].
Çàìå÷àíèå 1. Äëÿ àïïðîêñèìàöèîííî-óñòîé÷èâûõ ïðåäèêàòîâ P ïîðîã îòíî-
øåíèÿ àïïðîêñèìàöèè ïðîáëåìû Max CSP P� � äîñòèãàåòñÿ (òåîðåìà 2) è ðàâåí
d P Pk( ) | ( )|� � �2 11 .
Ýòî çíà÷åíèå áóäåì íàçûâàòü ïîðîãîâûì «ñëó÷àéíûì» îòíîøåíèåì àïïðîê-
ñèìàöèè ïðåäèêàòà P.
Èìåþò ìåñòî ñëåäóþùèå ðåçóëüòàòû ïî àïïðîêñèìàöèîííî-óñòîé÷èâûì
ïðåäèêàòàì ïðîáëåìû Max EkCSP P� � . Íå ñóùåñòâóåò ïðåäèêàòîâ ðàçìåðíîñòè
2(k � 2), êîòîðûå ÿâëÿþòñÿ àïïðîêñèìàöèîííî-óñòîé÷èâûìè [15]. Ïðè k � 3 ïðî-
áëåìà Max E LIN� �3 ÿâëÿåòñÿ íàñëåäñòâåííî àïïðîêñèìàöèîííî-óñòîé÷èâîé
[8], è ýòî èñ÷åðïûâàåò âñå àïïðîêñèìàöèîííî-óñòîé÷èâûå ïðåäèêàòû ðàçìåðíî-
ñòè 3 [17]. Àïïðîêñèìàöèîííî-óñòîé÷èâûå ïðåäèêàòû ðàçìåðíîñòè 4 (k � 4) èñ-
ñëåäîâàíû â ðàáîòå [16], ãäå ñóùåñòâóåò 400 ðàçëè÷íûõ ïðåäèêàòîâ (ñ òî÷íîñòüþ
äî ïåðåñòàíîâêè ïåðåìåííûõ è èõ îòðèöàíèé). Èç íèõ 79 èäåíòèôèöèðîâàíû êàê
àïïðîêñèìàöèîííî-óñòîé÷èâûå; 275 — êàê íåàïïðîêñèìàöèîííî-óñòîé÷èâûå;
ñòàòóñ îñòàâøèõñÿ 46 ïðåäèêàòîâ îïðåäåëèòü íå óäàëîñü.
Ïðèâåäåì îñíîâíûå ðåçóëüòàòû äëÿ àïïðîêñèìàöèîííî-óñòîé÷èâûõ ïðåäè-
êàòîâ ðàçìåðíîñòè 3 (Max E CSP P� �3 ).
Òåîðåìà 3 [8]. Äëÿ ïðîèçâîëüíîãî �� 0 ÿâëÿåòñÿ NP-òðóäíûì àïïðîêñèìè-
ðîâàòü ïðîáëåìó Max E LIN� �3 ñ îòíîøåíèåì
1
2
� �. Èíûìè ñëîâàìè, ïðîáëåìà
Max E LIN� �3 àïïðîêñèìàöèîííî-óñòîé÷èâà.
Òåîðåìà 4 [8]. Äëÿ ïðîèçâîëüíîãî �� 0 ÿâëÿåòñÿ NP-òðóäíûì àïïðîêñèìè-
ðîâàòü ïðîáëåìó Max E SAT� �3 ñ îòíîøåíèåì
7
8
� �. Èíûìè ñëîâàìè, ïðîáëåìà
Max E SAT� �3 àïïðîêñèìàöèîííî-óñòîé÷èâà.
Òåîðåìà 5 [8]. Ïóñòü P — ïðåäèêàò îò òðåõ ïåðåìåííûõ òàêîé, ÷òî
P x y z( , , ) �1 äëÿ ïðîèçâîëüíûõ x y z, , , óäîâëåòâîðÿþùèõ óðàâíåíèþ xyz �1 , òîãäà
ïðîáëåìà CSP, îïðåäåëÿåìàÿ ñ ïîìîùüþ P, àïïðîêñèìàöèîííî-óñòîé÷èâà.
Òåîðåìà 5 îñòàåòñÿ ïðàâèëüíîé ïðè çàìåíå óðàâíåíèÿ xyz �1 íà xyz � �1 .
Îáîáùåíèåì òåîðåìû 5 åñòü ñëåäóþùàÿ òåîðåìà.
92 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2012, ¹ 1
Òåîðåìà 6 [10]. Ïðåäèêàò P îò òðåõ ïåðåìåííûõ ÿâëÿåòñÿ àïïðîêñèìàöèîí-
íî-óñòîé÷èâûì òîãäà è òîëüêî òîãäà, êîãäà îí ÿâëÿåòñÿ ñëåäñòâèåì íå÷åòíîãî
èëè ÷åòíîãî ïàðèòåòà.
Ââåäåì ñëåäóþùèå òðåõìåñòíûå ïðåäèêàòû [17]:
XOR x x x x x x( , , )1 2 3 1 2 3�
, NTW x x x x x x x x x( , , ) ( ) ( )1 2 3 1 2 3 1 2 3� � � � ,
OXR x x x x x x( , , ) ( )1 2 3 1 2 3� �
, OR x x x x x x( , , )1 2 3 1 2 3� � � .
Ïðèâåäåííûå âûøå ðåçóëüòàòû ìîæíî îáîáùèòü â âèäå ñëåäóþùåãî
óòâåðæäåíèÿ.
Òåîðåìà 7. Ïðåäèêàòû XOR NTW OXR OR, , , ÿâëÿþòñÿ àïïðîêñèìàöèîí-
íî-óñòîé÷èâûìè ïðåäèêàòàìè. Èç íèõ XOR NTW OXR, , — íàñëåäñòâåííî àïïðîê-
ñèìàöèîííî-óñòîé÷èâûå ïðåäèêàòû.
Ïóñòü Max EkCSP P� � — ïðîèçâîëüíàÿ íåâçâåøåííàÿ CSP-ïðîáëåìà
( , [ ])w i mi � �1 . Ïóñòü I — ïðîèçâîëüíûé ýêçåìïëÿð ïðîáëåìû Max EkCSP P� � ,
ýêçåìïëÿð I � ýòîé ïðîáëåìû îáðàçóåòñÿ èç ýêçåìïëÿðà I äîáàâëåíèåì ïðîèçâîëü-
íîãî ( )m�1 -ãî îãðàíè÷åíèÿ
z z zm
i
m
i
m
k
( ) ( ) ( )( , , )� � ��1 1 1
1
� , z x x x x j k
i
m
n n
j
( ) , , , , , , [ ]� � �1
1 1{ }� � .
Îïðåäåëèì ðåîïòèìèçàöèîííûé âàðèàíò ïðîáëåìû Max EkCSP P� � .
Ïðîáëåìà Ins Max EkCSP P� � � . Âõîäíûå äàííûå. Ïðîèçâîëüíûé ýêçåìï-
ëÿð I ïðîáëåìû Max EkCSP P� � , x * — îïòèìàëüíîå ðåøåíèå ýêçåìïëÿðà I .
Ðåçóëüòàò. Íàéòè îïòèìàëüíîå ðåøåíèå ýêçåìïëÿðà I �, ïîëó÷åííîãî èñõîäÿ
èç ýêçåìïëÿðà I (êàê îïèñàíî âûøå) ïðîáëåìû Max EkCSP P� � , èñïîëüçóÿ x * .
Öåëü. Íàéòè x, êîòîðîå ìàêñèìèçèðóåò ÷èñëî âûïîëíåííûõ îãðàíè÷åíèé ýê-
çåìïëÿðà I �.
Ïîñêîëüêó ïðîáëåìà Max EkCSP P� � ÿâëÿåòñÿ NP-òðóäíîé äëÿ k � 2, òî
ëåãêî ïîêàçàòü, ÷òî òàêîâîé áóäåò è Ins Max EkCSP P� � � .
ÍÅÊÎÒÎÐÛÅ ÑÂÅÄÅÍÈß ÈÇ ÄÈÑÊÐÅÒÍÎÃÎ ÀÍÀËÈÇÀ ÔÓÐÜÅ
ÁÓËÅÂÛÕ ÔÓÍÊÖÈÉ È ÒÅÎÐÈÈ PCP-ÑÈÑÒÅÌ
Ïðèâåäåííàÿ íèæå èíôîðìàöèÿ âçÿòà èç [18, 19]. Áóäåì ðàññìàòðèâàòü áóëåâû
ôóíêöèè êàê îòîáðàæåíèÿ f n: , ,{ } { }0 1 0 1
. Åñëè èíòåðïðåòèðîâàòü 0 è 1, êàê
1 è –1, òî ïîëó÷èì òàêîå ïðåäñòàâëåíèå áóëåâûõ ôóíêöèé: f n: , ,{ } { }�
�1 1 1 1 .
Ñóùåñòâóåò ñëåäóþùèé ñïîñîá, ïðåäñòàâëÿþùèé f â âèäå ïîëèíîìà. Òàê, äëÿ
n � 3 ðàññìîòðèì ôóíêöèþ «majority» («áîëüøèíñòâî»)
Maj x Maj x x x Maj3 3 1 2 3 3 1 1 1 1( ) ( , , ): ( , , ) ,� �
Maj Maj3 31 1 1 1 1 1 1 1( , , ) , , ( , , )� � � � � � �� .
Äëÿ x x x x� ( , , )1 2 3 ìîæíî çàïèñàòü
Maj x
x x x
3
1 2 31
2
1
2
1
2
1( ) ( )�
��
�
�
�
�
�
��
�
�
�
�
�
��
�
�
�
�
� � �
�
��
�
�
�
�
�
��
�
�
�
�
�
��
�
�
�
�
� � � �
��
�
�
�1
2
1
2
1
2
1
1
2
1 2 3 1x x x x
( ) �
�
�
��
�
�
�
�
�
��
�
�
�
�
� �
1
2
1
2
12 3x x
( ) .
Ïîñëå óìíîæåíèÿ âûðàæåíèé â ñêîáêàõ è ñâåäåíèÿ ïîäîáíûõ ÷ëåíîâ ìîæíî
ïîëó÷èòü
Maj x x x x x x x3 1 2 3 1 2 3
1
2
1
2
1
2
1
2
( ) � � � � . (1)
ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2012, ¹ 1 93
Àíàëîãè÷íóþ ïðîöåäóðó ìîæíî âûïîëíèòü äëÿ ïðîèçâîëüíîé ôóíêöèè
f Rn: ,{ }�
1 1 (R — ìíîæåñòâî äåéñòâèòåëüíûõ ÷èñåë), óìíîæàÿ ñîîòâåòñòâóþ-
ùèé x-èíòåðïîëÿòîð íà çíà÷åíèå f x( ) .
Ïðåäëîæåíèå 1. Ïðîèçâîëüíàÿ ôóíêöèÿ f Rn: ,{ }�
1 1 ìîæåò áûòü åäèí-
ñòâåííûì îáðàçîì ïðåäñòàâëåíà â âèäå ïîëèíîìà
f x c xS
S n
i
i S
( ) ,
[ ]
�
� �
� � (2)
ãäå [ ] , ,n n� { }1 � . Ôîðìóëà (2) íàçûâàåòñÿ ôîðìóëîé Ôóðüå äëÿ f .
Òðàäèöèîííî êîýôôèöèåíòû cS îáîçíà÷èì êàê � ( )f S , à xi
i S�
� — êàê �S x( ) .
Òîãäà ïîëó÷èì
f x f S xS
S n
( ) � ( ) ( )
[ ]
�
�
� � .
Ðàññìîòðèì ïðîñòðàíñòâî G g g R� �
{ { } }| : ,1 1 . Îïðåäåëèì â G ñêàëÿðíîå
ïðîèçâåäåíèå:
� � � �
� �
�f g f x g x
n
x n
, ( ) ( )
,
1
2 1 1{ }
.
Ëèíåéíûå ôóíêöèè �S x( ) äëÿ ðàçëè÷íûõ ïîäìíîæåñòâ S ôîðìèðóþò îðòî-
íîðìèðîâàííûé áàçèñ ïî îòíîøåíèþ ê ââåäåííîìó ñêàëÿðíîìó ïðîèçâåäåíèþ.
Î÷åâèäíî, ÷òî äëÿ âñåõ S n� [ ] è ïðîèçâîëüíîãî x n� �{ }1 1, èìååì
� � � �� � �S S S x, , | ( )|1 1 . Âûïîëíÿþòñÿ ñëåäóþùèå ïðåäëîæåíèÿ.
Ïðåäëîæåíèå 2: 1) åñëè S T� , òî � � �� �S T, 0;
2) � ( ) , ( ) ( )
,
f S f f x xS n S
x n
� � � � �
� �
�� �
1
2 1 1{ }
.
Áóäåì ðàññìàòðèâàòü x x xn� ( , , )1 � êàê ñëó÷àéíóþ ñòðîêó, ðàâíîìåðíî ðàñ-
ïðåäåëåííóþ íà { }�1 1, n . Òàêàÿ ñëó÷àéíàÿ ñòðîêà x x xn� ( , , )1 � áóäåò ãåíåðèðî-
âàòüñÿ âûáîðîì êàæäîãî xi íåçàâèñèìî è ðàâíîâåðîÿòíî ñ { }�1 1, . ×åðåç E f x
x
[ ( )]
áóäåì îáîçíà÷àòü ìàòåìàòè÷åñêîå îæèäàíèå ñëó÷àéíîé áóëåâîé ôóíêöèè f x( )
îòíîñèòåëüíî ðàñïðåäåëåíèÿ x.
Òåîðåìà 8 (Ïàðñåâàëÿ). Äëÿ ïðîèçâîëüíîé f Rn: ,{ }�
1 1
� ( ) [ ( ) ]
[ ]
f S E f x
S n x
2 2
�
� � .
Ïðåäëîæåíèå 3: 1) � � �S T S Tx x x( ) ( ) ( )� � , ãäå S T� — ñèììåòðè÷åñêàÿ ðàç-
íîñòü S è T ;
2) � � �S S Sxy x y( ) ( ) ( )� ;
3) E x
U
x
U[ ( )]
, ,
� �
��
!
"
0
1
åñëè
4) äëÿ ïðîèçâîëüíûõ f Rn: ,{ }�
1 1 è S n� [ ] èìååì � ( ) [ ( ) ( )]f S E f x x
x
S� � ;
5) åñëè f n: , ,{ } { }�
�1 1 1 1 , òî � ( )
[ ]
f S
S n
2 1
�
� � (ñëåäñòâèå èç òåîðåìû 8 — ðà-
âåíñòâî Ïàðñåâàëÿ).
Îïðåäåëåíèå 9. Äëÿ äàííîãî 0 1# #� áóäåì ñ÷èòàòü, ÷òî x y n, ,� �{ }1 1 åñòü
( )1 2� � -êîððåëèðîâàííûå ñëó÷àéíûå âåêòîðû, åñëè x — ðàâíîìåðíî ðàñïðåäåëåí-
íûé, à y ãåíåðèðóåòñÿ ñ ïîìîùüþ x îòðèöàíèåì êàæäîãî áèòà íåçàâèñèìî ñ âåðî-
ÿòíîñòüþ �.
94 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2012, ¹ 1
èíà÷å;
Ëåãêî óâèäåòü, ÷òî E x y x y x yi i i i i i[ ] [ ] [ ]� � � � � �Pr Pr 1 2�, îòêóäà ñëåäóåò
( )1 2� � -êîððåëèðîâàííîñòü.
Äàëåå áóäåì èñïîëüçîâàòü èíôîðìàöèþ èç ðàáîòû [19]. Ïóñòü P — ïðîèç-
âîëüíàÿ îïòèìèçàöèîííàÿ (äëÿ îïðåäåëåííîñòè íà ìàêñèìóì) ïðîáëåìà. Ïîä
( , )c s gap� âåðñèåé ïðîáëåìû P (îáîçíà÷åíèå GapPc s, ) áóäåì ïîíèìàòü ïðîáëåìó,
äëÿ êîòîðîé ëèáî OPT( )I c� , ëèáî OPT( )I s# äëÿ ïðîèçâîëüíîãî ýêçåìïëÿðà
I P� . Ðàññìîòðèì NP-ïîëíóþ ïðîáëåìó 3SAT(3-âûïîëíèìîñòü). Ïðîèçâîëüíàÿ
3SAT-ôîðìóëà (E CNF3� -ôîðìóëà) — ýòî êîíúþíêöèÿ ìíîæåñòâà ñêîáîê, ãäå
êàæäàÿ ñêîáêà åñòü äèçúþíêöèÿ òðåõ áóëåâûõ ïåðåìåííûõ èëè èõ îòðèöàíèé.
Ñóòü ïðîáëåìû ñîñòîèò â ïðèïèñûâàíèè áóëåâûì ïåðåìåííûì òàêèõ çíà÷åíèé
èñòèííîñòè, ÷òî ôîðìóëà ñòàíîâèòñÿ ëîãè÷åñêè èñòèííîé (âûïîëíèìîé). Áóäåì
ñ÷èòàòü, ÷òî CNF -ôîðìóëà � ñ m ñêîáêàìè c-âûïîëíèìà (c�[ , ]0 1 ) òîãäà è òîëüêî
òîãäà, êîãäà íåêîòîðîå ïðèïèñûâàíèå âûïîëíÿåò íå áîëåå cm ñêîáîê.
Äîïóñòèì, ÷òî ñóùåñòâóåò ïîëèíîìèàëüíàÿ ñâîäèìîñòü îò 3SAT ê GapPc s,
äëÿ íåêîòîðûõ 0 s c, ò.å. ñâîäèìîñòü, êîòîðàÿ îòîáðàæàåò 3SAT-ôîðìóëó � íà
ýêçåìïëÿð I ïðîáëåìû P. Ïðè ýòîì åñëè � èìååò ïðèïèñûâàíèå, êîòîðîå äåëàåò
åå âûïîëíèìîé, òî OPT( )I c� .  ïðîòèâíîì ñëó÷àå OPT( )I s# .
Òàêàÿ ñâîäèìîñòü ïðåäïîëàãàåò, ÷òî åñëè ñóùåñòâóåò ïîëèíîìèàëüíûé àëãî-
ðèòì ñ îòíîøåíèåì àïïðîêñèìàöèè ñòðîãî áîëüøèì, ÷åì
s
c
äëÿ ïðîáëåìû P, òî
ñóùåñòâóåò âîçìîæíîñòü ýôôåêòèâíî îïðåäåëèòü, âûïîëíèìà ëè 3SAT-ôîðìóëà,
ò.å. P NP� . Òàêèì îáðàçîì, ïðè ñòàíäàðòíîì ïðåäïîëîæåíèè P NP� ýòà ñâîäè-
ìîñòü ÿâëÿåòñÿ èñòî÷íèêîì ïîëó÷åíèÿ ðåçóëüòàòîâ ïî íåàïïðîêñèìèðóåìîñòè
äëÿ ïðîáëåìû P.
Íà ïðàêòèêå ñâîäèìîñòü, îïèñàííàÿ âûøå, ïðåäñòàâëÿåò ïîñëåäîâàòåëüíîñòü
ñâîäèìîñòåé. Ïðè÷åì ïåðâàÿ ñâîäèìîñòü â ýòîé ïîñëåäîâàòåëüíîñòè — èçâåñò-
íàÿ PCP-òåîðåìà (Probabilistic Checkable Proof, âåðîÿòíîñòíî ïðîâåðÿåìûå äîêà-
çàòåëüñòâà), êîòîðàÿ èìååò ìíîæåñòâî ôîðìóëèðîâîê.  äàííîì ñëó÷àå îíà ìî-
æåò áûòü ñôîðìóëèðîâàíà êàê ñâîäèìîñòü îò 3SAT ê gap — âåðñèè 3SAT . Òàê,
äëÿ �-ôîðìóëû ïóñòü OPT( )� îáîçíà÷àåò ìàêñèìàëüíóþ ÷àñòü ñêîáîê, êîòîðûå
ìîãóò áûòü âûïîëíåíû â ðåçóëüòàòå ïðîèçâîëüíîãî ïðèïèñûâàíèÿ. Òàêèì îáðà-
çîì, OPT( )� �1 òîãäà è òîëüêî òîãäà, êîãäà � âûïîëíèìà. PCP-òåîðåìà óòâåðæ-
äàåò, ÷òî ñóùåñòâóþò óíèâåðñàëüíàÿ êîíñòàíòà � 1 è ïîëèíîìèàëüíàÿ ñâîäè-
ìîñòü, êîòîðàÿ îòîáðàæàåò ýêçåìïëÿð 3SAT-ôîðìóëû � íà äðóãîé ýêçåìïëÿð
3SAT-ôîðìóëû �, ïðè ýòîì:
1) åñëè OPT( )� �1 , òî OPT( )� �1 (ïîëíîòà (Completeness));
2) åñëè OPT( )� 1 , òî OPT( )� �# (êîððåêòíîñòü (Soundness)).
Îòñþäà ñëåäóåò, ÷òî ïðîáëåìà Max SAT�3 íåàïïðîêñèìèðóåìà ñ îòíîøåíèåì
àïïðîêñèìàöèè � 1 . PCP-òåîðåìà áûëà ïðåäñòàâëåíà âûøå â êà÷åñòâå êîìáè-
íàòîðíîé ñâîäèìîñòè. Ñóùåñòâóåò ýêâèâàëåíòíàÿ ôîðìóëèðîâêà â òåðìèíàõ
ïðîâåðêè äîêàçàòåëüñòâ (proof checking). Òåîðåìà óòâåðæäàåò, ÷òî êàæäîå
NP-óòâåðæäåíèå èìååò ïîëèíîìèàëüíîå äîêàçàòåëüñòâî, êîòîðîå ìîæåò áûòü
ïðîâåðåíî ïîëèíîìèàëüíûì âåðîÿòíîñòíûì ïðîâåðÿþùèì (verifier), ñ÷èòû-
âàþùèì òîëüêî êîíñòàíòíîå ÷èñëî áèò â äîêàçàòåëüñòâå. Ïðîâåðÿþùèé èìååò
ñâîéñòâà ïîëíîòû è êîððåêòíîñòè: êàæäîå äîêàçàòåëüñòâî êîððåêòíîãî óòâåðæäå-
íèÿ ïðèíèìàåòñÿ ñ âåðîÿòíîñòüþ åäèíèöà, è êàæäîå äîêàçàòåëüñòâî íåêîððåêòíî-
ãî óòâåðæäåíèÿ ïðèíèìàåòñÿ ñ ìàëîé âåðîÿòíîñòüþ (íàïðèìåð, íå áîëüøåé 1%).
Òàêèì îáðàçîì, êîìáèíàòîðíàÿ ñâîäèìîñòü è ïðîâåðêà äîêàçàòåëüñòâ ÿâëÿþòñÿ
ìåòîäàìè äëÿ óñòàíîâëåíèÿ íåàïïðîêñèìèðóåìîñòè îïòèìèçàöèîííûõ ïðîáëåì.
Äëÿ îïèñàíèÿ ýòèõ ìåòîäîâ ïðèâåäåì ôîðìàëüíûå îïðåäåëåíèÿ [8]. Áóäåì
îïðåäåëÿòü ñèñòåìû äîêàçàòåëüñòâ (proof systems) ñ ïîìîùüþ ñâîéñòâ ïðîâåðÿþ-
ùåãî (verifier). Äëÿ ïðîâåðêè óòâåðæäåíèé ïðîâåðÿþùåìó íåîáõîäèìû ïîìîù-
íèêè. Áóäåì ñ÷èòàòü, ÷òî îí èìååò äîñòóï ê îäíîìó èëè íåñêîëüêèì îðàêóëàì —
ôóíêöèÿì. Âî ìíîãèõ âàðèàíòàõ ñèñòåì äîêàçàòåëüñòâ îáñóæäàþòñÿ ïîíÿòèÿ äî-
êàçûâàþùèõ (proovers (ïðóâåðû)) è çàïèñàííûõ äîêàçàòåëüñòâ (written proofs).
ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2012, ¹ 1 95
Çàïèñàííûå äîêàçàòåëüñòâà ýêâèâàëåíòíû äîêàçàòåëüñòâàì, èñïîëüçóþùèõ îðà-
êóëû, ãäå ñ÷èòûâàíèå i-ãî áèòà ñîîòâåòñòâóåò âîïðîñó ê îðàêóëó. Îòìåòèì, ÷òî
ïðóâåðû áîëåå ìîùíûå, ÷åì îðàêóëû, ïîñêîëüêó ìîãóò áûòü ñëó÷àéíûìè è
èñòîðè÷åñêè çàâèñèìûìè.
Îïðåäåëåíèå 10. Îðàêóë åñòü ôóíêöèÿ $* ,
{ }0 1 (ãäå $*— ìíîæåñòâî êî-
íå÷íûõ ñòðîê â àëôàâèòå $ ).
Òèïè÷íûé ïðîâåðÿþùèé V x r� ( , ) ïðåäñòàâëÿåò âåðîÿòíîñòíóþ ìàøèíó
Òüþðèíãà, ãäå � — îðàêóë, x — ââîä, r — âíóòðåííÿÿ ñëó÷àéíàÿ ëåíòà. Ñ÷èòàþò,
÷òî ïðîâåðÿþùèé ïðèíèìàåò ðåøåíèå, åñëè îí âûâîäèò åäèíèöó (V x r� ( , ) �1),
èíà÷å îí îòâåðãàåò ðåøåíèå.
Îïðåäåëåíèå 11. Ïóñòü c è s — äåéñòâèòåëüíûå ÷èñëà òàêèå, ÷òî
0 1# #s c . Ïîëèíîìèàëüíàÿ âåðîÿòíîñòíàÿ ìàøèíà Òüþðèíãà V — åñòü ïðîâå-
ðÿþùèé â âåðîÿòíîñòíî-ïðîâåðÿåìîì äîêàçàòåëüñòâå ñ ïîëíîòîé c è êîððåêòíî-
ñòüþ s äëÿ ÿçûêà L òîãäà è òîëüêî òîãäà, êîãäà
• äëÿ x L� ñóùåñòâóåò îðàêóë � òàêîé, ÷òî Pr
r
V x r c[ ( , ) ]� � �1 ;
• äëÿ x L% è âñåõ � èìååì Pr
r
V x r s[ ( , ) ]� � #1 .
Îïðåäåëåíèå 12. Ïðîâåðÿþùèé V èñïîëüçóåò ëîãàðèôìè÷åñêóþ ñëó÷àé-
íîñòü, åñëè ñóùåñòâóåò àáñîëþòíàÿ êîíñòàíòà c òàêàÿ, ÷òî äëÿ êàæäîãî âõîäà x è
äîêàçàòåëüñòâà îðàêóëà � äëèíà ñëó÷àéíîé ñòðîêè r, êîòîðóþ èñïîëüçóåò V � ,
îöåíèâàåòñÿ ñâåðõó êàê c xlog| | .
Îïðåäåëåíèå 13. Ïðîâåðÿþùèé V ñ÷èòûâàåò c áèò â âåðîÿòíîñòíî-ïðîâåðÿ-
åìîì äîêàçàòåëüñòâå, åñëè äëÿ êàæäîãî ðåçóëüòàòà ñëó÷àéíûõ èñïûòàíèé è êàæ-
äîãî äîêàçàòåëüñòâà � ïðîâåðÿþùèé V � çàäàåò íå áîëåå c âîïðîñîâ îðàêóëó.
Òåîðåìà 9 (PCP-òåîðåìà) [8]. Ñóùåñòâóåò óíèâåðñàëüíîå öåëîå c òàêîå, ÷òî ÿçûê
â NP èìååò PCP ïðîâåðÿþùåãî V ñ ïîëíîòîé åäèíèöà è êîððåêòíîñòüþ
1
2
, ãäå V èñ-
ïîëüçóåò ëîãàðèôìè÷åñêóþ ñëó÷àéíîñòü è ñ÷èòûâàåò íå áîëåå c áèò â äîêàçàòåëüñòâå.
Òåîðåìà 10 (âàðèàíò PCP-òåîðåìû) [8]. Ïóñòü L — ÿçûê â NP è x— ñòðîêà.
Ñóùåñòâóåò óíèâåðñàëüíàÿ êîíñòàíòà c 1 òàêàÿ, ÷òî çà âðåìÿ, ïîëèíîìèàëüíîå
îòíîñèòåëüíî | |x , ìîæíî ñêîíñòðóèðîâàòü ôîðìóëó � x L, E CNF3� òàêóþ, ÷òî
åñëè x L� , òî � x L, âûïîëíèìà; åñëè x L% , òî � x L,
íå áîëåå ÷åì c-âûïîëíèìà.
Êðîìå òîãî, êàæäàÿ ïåðåìåííàÿ âñòðå÷àåòñÿ â ôîðìóëå òî÷íî ïÿòü ðàç.
Îïèøåì îäíîðàóíäîâóþ èíòåðàêòèâíóþ ñèñòåìó äîêàçàòåëüñòâ ñ äâóìÿ
ïðóâåðàìè (two prover one-round proof system, ñîêðàùåííî 2P1R-ñèñòåìà). Ïðîâå-
ðÿþùèé â òàêîé ñèñòåìå èìååò äîñòóï ê äâóì îðàêóëàì è ìîæåò çàäàòü îäèí
âîïðîñ êàæäîìó èç íèõ.
Ïîñêîëüêó ïðîâåðÿþùèé ðàáîòàåò â ïîëèíîìèàëüíîå âðåìÿ, òî îí íå ìîæåò
ñ÷èòàòü áîëüøå, ÷åì ïîëèíîìèàëüíîå ÷èñëî áèò. Ïóñòü P P1 2, — äâà îðàêóëà è
q q1 2, — äâà âîïðîñà. Îðàêóëû èìåþò äîñòóï òîëüêî ê ýòèì âîïðîñàì, è åñëè V
ïðèíèìàåò ðåøåíèå, òî V x r P q P q( , , ( ), ( ))1 1 2 2 1� .
Îïðåäåëåíèå 14. Ïóñòü c s, — äåéñòâèòåëüíûå ÷èñëà, 0 1# #s c . Ïîëèíî-
ìèàëüíàÿ âåðîÿòíîñòíàÿ ìàøèíà Òüþðèíãà V ñ äâóìÿ îðàêóëàìè — ýòî ïðîâåðÿ-
þùèé â 2P1R-ñèñòåìå ñ ïîëíîòîé c è êîððåêòíîñòüþ s äëÿ ÿçûêà L , åñëè íà âõîäå
x îíà ôîðìèðóåò (áåç ñîãëàñèÿ ñî ñâîèìè îðàêóëàìè) äâå ñòðîêè q q1 2, òàêèå, ÷òî
• äëÿ x L� ñóùåñòâóþò äâà îðàêóëà P P1 2, òàêèå, ÷òî Pr
r
V x r P q[ ( , , ( ),1 1
P q c2 2 1( )) ]� � ;
• äëÿ x L% è ëþáûõ îðàêóëîâ P P1 2, èìååì Pr
r
V x r P q[ ( , , ( ),1 1 P q s2 2 1( )) ]� # .
96 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2012, ¹ 1
 îáîèõ ñëó÷àÿõ q q1 2, — âîïðîñû, êîòîðûå V çàäàåò îðàêóëàì, P q1 1( ) çàâè-
ñèò îò x, íî íå çàâèñèò îò q2 . Àíàëîãè÷íàÿ ñèòóàöèÿ èìååò ìåñòî äëÿ P q2 2( ) .
Èñïîëüçóÿ îäíîðàóíäîâûé ïðîòîêîë ñ êîððåêòíîñòüþ s, ñîãëàñíî îïðåäåëå-
íèþ 14 ìîæíî ïîâòîðèòü åãî ïîñëåäîâàòåëüíî äâàæäû. Òîãäà êîððåêòíîñòü
óëó÷øèòñÿ (óìåíüøèòñÿ) äî s2 . Ïîñëåäîâàòåëüíî ïîâòîðÿÿ ïðîòîêîë u ðàç, ïîëó-
÷àåì êîððåêòíîñòü su .  ðåçóëüòàòå ïîëó÷èì ìíîãîðàóíäîâûé ïðîòîêîë. ×òîáû
îí íå èçìåíèëñÿ, ïðèìåíèì òåõíèêó ïàðàëëåëüíûõ ïîâòîðîâ. Ïðîâåðÿþùèé V
ïîâòîðÿåò ñâîè ñëó÷àéíûå âûáîðû u ðàç äëÿ ïîëó÷åíèÿ u íåçàâèñèìûõ ïàð âîï-
ðîñîâ ( , )( ) ( )q qi i
i
u
1 2 1� è ïîñûëàåò ( )( )q i
i
u
1 1� ê P1, à ( )( )q i
i
u
2 1� — ê P2 .
Çàòåì V ïîëó÷àåò u îòâåòîâ îò êàæäîãî ïðóâåðà è ïðèíèìàåò èõ òàê, êàê
áóäòî îí ðàáîòàåò â îäíîðàóíäîâîé ñèñòåìå u ðàç. Êîððåêòíîñòü òàêîãî ïðîòîêî-
ëà ìîæåò áûòü áîëüøå su . Îäíàêî Ðàö (Raz) [20] äîêàçàë, ÷òî ïðè ìàëîì ðàçìåðå
îòâåòà êîððåêòíîñòü ýêñïîíåíöèàëüíî óìåíüøàåòñÿ îòíîñèòåëüíî u.
Òåîðåìà 11 [20]. Äëÿ âñåõ öåëûõ d è s 1ñóùåñòâóåò cd s, 1òàêàÿ, ÷òî äëÿ äàí-
íîé 2P1R-ñèñòåìû ïðè êîððåêòíîñòè s è ñ ðàçìåðàìè îòâåòîâ, íå á�ëüøèìè d, äëÿ
âñåõ öåëûõ u êîððåêòíîñòü ïðîòîêîëîâ, ðàáîòàþùèõ ïàðàëëåëüíî, íå áîëüøå c
d s
u
,
.
Îïðåäåëåíèå 15. Îáîçíà÷èì ÷åðåç 2Ð1R c s r n, ( ( ))-êëàññ ÿçûêîâ L, äëÿ êîòî-
ðûõ ñóùåñòâóåò 2P1R-ñèñòåìà ñ ïðîâåðÿþùèì V , êîòîðîìó äîñòóïíî ñëó÷àéíîå
÷èñëî r n( ) áèò.
Òåîðåìà 12 [21]. Ñóùåñòâóåò êîíñòàíòà �P � 0 òàêàÿ, ÷òî NP n
P
� �2 1 1 1P R log, ( )� .
ÏÎÐÎÃ ÎÒÍÎØÅÍÈß ÀÏÏÐÎÊÑÈÌÀÖÈÈ ÄËß ÐÅÎÏÒÈÌÈÇÀÖÈÈ
ÀÏÏÐÎÊÑÈÌÀÖÈÎÍÍÎ-ÓÑÒÎÉ×ÈÂÛÕ ÏÐÎÁËÅÌ
Òåîðåìà 13. Äëÿ ïðîáëåìû Ins Max EkCSP P� � � (ðåîïòèìèçàöèÿ
Max EkCSP P� � ) ñóùåñòâóåò ïîëèíîìèàëüíûé ïðèáëèæåííûé àëãîðèòì ñ îò-
íîøåíèåì àïïðîêñèìàöèè q P
P
k
k
( )
| ( )|
�
�� �
2
2 11 1
, åñëè k O n� ( )log .
Äîêàçàòåëüñòâî. Ïðèìåíèì ïîäõîä, ðàññìîòðåííûé â [23]. Ïóñòü I — ýê-
çåìïëÿð ïðîáëåìû Max EkCSP P� � , êîòîðûé ñîñòîèò èç ñèñòåìû îãðàíè÷åíèé
C z i mi� �{ }( ) , [ ] è îïòèìàëüíîãî ðåøåíèÿ x * ; w x( )* — ÷èñëî âûïîëíåííûõ îãðà-
íè÷åíèé â ñèñòåìå C ðåøåíèåì x *. Ê ñèñòåìå äîáàâëåíî îãðàíè÷åíèå z m( )�1 ,
â ðåçóëüòàòå ïîëó÷àåì ýêçåìïëÿð I � ïðîáëåìû Max EkCSP P� � . Ïóñòü xI �
* — åãî
îïòèìàëüíîå ðåøåíèå. Åñëè xI �
* íå âûïîëíÿåò îãðàíè÷åíèÿ z m( )�1 , òî x *åñòü
îïòèìàëüíîå ðåøåíèå ýêçåìïëÿðà I � ïðîáëåìû Ins Max EkCSP P� � � , îòñþäà
w x w xI( ) ( ) .* *� �� 1 (3)
Èç ëåâîé ÷àñòè íåðàâåíñòâà ñëåäóåò, ÷òî x * — îïòèìàëüíîå ðåøåíèå I �, à èç
ïðàâîé ÷àñòè — ÷òî îïòèìàëüíîå ðåøåíèå íå âûïîëíÿåò îãðàíè÷åíèÿ z m( )�1 .
Ïóñòü xI �
* âûïîëíÿåò îãðàíè÷åíèå z m( )�1 è ïðåäñòàâëÿåò l âàðèàíòîâ, ïðè êî-
òîðûõ áóäåò âûïîëíåíî îãðàíè÷åíèå z m( )�1 (î÷åâèäíî, ÷òî l k 2 ). Ïîñòðîèì l
ïðèáëèæåííûõ ðåøåíèé x i li ( [ ])� ñëåäóþùèì îáðàçîì. Âûáåðåì i-å ïðèïèñû-
âàíèå, êîòîðîå âûïîëíÿåò îãðàíè÷åíèå z m( )�1 . Èç ñèñòåìû îãðàíè÷åíèé óäà-
ëÿåì z m( )�1 è ê îñòàâøèìñÿ îãðàíè÷åíèÿì (ó÷èòûâàÿ ðåçóëüòàò ïðèïèñûâà-
íèÿ) ïðèìåíÿåì íåêîòîðûé ïîëèíîìèàëüíûé -ïðèáëèæåííûé àëãîðèòì. Ïî-
ëó÷àåì ïðèáëèæåííîå ðåøåíèå x i . Òîãäà
w x w x w xi
I I( ) ( ( ) ) ( )* *� � � � � �� � 1 1 1 . (4)
ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2012, ¹ 1 97
Óìíîæàÿ îáå ÷àñòè íåðàâåíñòâà (3) íà 1� è ñêëàäûâàÿ ñ (4), ïîëó÷àåì
( ) ( ) ( ) ( ) ( ) ( ) ( )* * *1 1 1 1� � � � � � � � � �� � w x w x w x w x wi
I I ( )*xI � .
Ñðåäè ðåøåíèé x * è x i âûáèðàåì íàèëó÷øåå (ò. å. ñ íàèáîëüøèì çíà÷åíèåì
öåëåâîé ôóíêöèè w) è îáîçíà÷àåì x. Èìååì
w x w x w x w xI
i( ) ( ) max ( ), ( ) ( ) ( )* *
� # � � � �1 1 2 { } ,
îòêóäà w x w xI( ) ( )*�
�
�
1
2
. Äëÿ ïîëèíîìèàëüíîñòè îïèñàííîãî àëãîðèòìà äî-
ñòàòî÷íî ïîòðåáîâàòü, ÷òîáû 2k cn# (n — îáùåå ÷èñëî ïåðåìåííûõ c � const),
îòêóäà ñëåäóåò k O n� ( )log â óñëîâèè òåîðåìû. Òàêèì îáðàçîì, â ðåçóëüòàòå
âûïîëíåíèÿ îïèñàííîãî àëãîðèòìà ïîëó÷åíî ïðèáëèæåííîå ðåøåíèå x ýêçåì-
ïëÿðà I � ñ îòíîøåíèåì àïïðîêñèìàöèè
1
2�
. Î÷åâèäíî, ÷òî âñåãäà
1
2�
�
( ) �1 . Ïîëîæèì � � � �d P Pk( ) | ( )|2 11 . Òîãäà, ïðèìåíèâ ïðèáëèæåííûé àë-
ãîðèòì èç òåîðåìû 1, ïîëó÷èì óòâåðæäåíèå äàííîé òåîðåìû.
Òåîðåìà 14. Åñëè ïðåäèêàò P ÿâëÿåòñÿ àïïðîêñèìàöèîííî-óñòîé÷èâûì è
äëÿ ïðîáëåìû Ins Max EkCSP P� � � ñóùåñòâóåò ïîëèíîìèàëüíî-ïðèáëèæåííûé
àëãîðèòì ñ îòíîøåíèåì àïïðîêñèìàöèè
, òî
# q P( ) .
Äîêàçàòåëüñòâî. Ïóñòü I — ýêçåìïëÿð ïðîáëåìû Max EkCSP P� � , êîòîðûé
ñîñòîèò èç ñèñòåìû îãðàíè÷åíèé C z i mi� �{ }( ) , [ ] è îïòèìàëüíîãî ðåøåíèÿ x * .
Ê ñèñòåìå äîáàâëÿåòñÿ îãðàíè÷åíèå z m( )�1 , â ðåçóëüòàòå ïîëó÷àåì ýêçåìïëÿð I � ïðî-
áëåìû Ins Max EkCSP P� � � . Ïóñòü x — ðåøåíèå ïðîáëåìû Ins Max EkCSP P� � � ,
ïîëó÷åííîå ñ ïîìîùüþ àëãîðèòìà èç äîêàçàòåëüñòâà òåîðåìû 13. Ðåøåíèå x ÿâ-
ëÿåòñÿ ëó÷øèì (áîëüøèì ïî çíà÷åíèþ öåëåâîé ôóíêöèè) èç ðåøåíèé x *è
x i l li k( [ ], )� 2 . Îíî ïîëó÷àåòñÿ ïîëèíîìèàëüíûì ïðèáëèæåííûì àëãîðèòìîì
ñ îòíîøåíèåì àïïðîêñèìàöèè �
( ) �
�
1
2
. Äîêàçàòåëüñòâî ïðîâåäåì îò ïðîòèâ-
íîãî. Ïóñòü
� q P( ) è �
( ) � . Ïîñêîëüêó ôóíêöèÿ � ( )ÿâëÿåòñÿ âîçðàñòàþùåé
ïî è �
�( ) ( ) ( ( ))� � �q P d P , òî îòñþäà ñëåäóåò, ÷òî � d P( ) . À ýòî ïðîòè-
âîðå÷èò òîìó ôàêòó, ÷òî ïðåäèêàò P àïïðîêñèìàöèîííî-óñòîé÷èâûé (ò. å. äëÿ ïî-
ëó÷åíèÿ ðåøåíèÿ êàêîãî-òî x i ïðèìåíÿëñÿ ïîëèíîìèàëüíûé àëãîðèòì ñ îòíîøå-
íèåì àïïðîêñèìàöèè, áîëüøèì d P( ) , ÷òî â ñèëó àïïðîêñèìàöèîííîé óñòîé÷è-
âîñòè ïðåäèêàòà P íåâîçìîæíî).
Òåîðåìà 15. Åñëè k O n� ( )log è ïðåäèêàò P àïïðîêñèìàöèîííî-óñòîé÷èâûé,
òî äëÿ ïðîáëåìû Ins Max EkCSP P� � � (ðåîïòèìèçàöèÿ Max EkCSP P� � ) ñóùå-
ñòâóåò ïîëèíîìèàëüíûé ïðèáëèæåííûé àëãîðèòì ñ îòíîøåíèåì àïïðîêñèìàöèè
q P
P
k
k
( )
| ( )|
�
�� �
2
2 11 1
. Äàííîå îòíîøåíèå àïïðîêñèìàöèè ÿâëÿåòñÿ ïîðîãîâûì.
Äîêàçàòåëüñòâî ñëåäóåò èç òåîðåì 13 è 14.
ÏÐÈÌÅÐÛ ÄËß ÒÐÅÕÌÅÑÒÍÛÕ ÏÐÅÄÈÊÀÒÎÂ
Êàæäûé ïðåäèêàò P îò òðåõ ïåðåìåííûõ ( )k � 3 ìîæíî åäèíñòâåííûì îáðàçîì
ïðåäñòàâèòü â âèäå ôîðìóëû Ôóðüå P x c x
S
P
S
i
i S
( )
[ ]
�
� �
� �
3
, ãäå c
S
P — êîýôôèöè-
åíòû Ôóðüå. Èìååòñÿ ñëåäóþùèé êðèòåðèé òîãî, ÷òî ïðåäèêàò P âñåãäà àï-
ïðîêñèìèðîâàí (îïðåäåëåíèå 7).
98 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2012, ¹ 1
Òåîðåìà 16 [10]. Ïðåäèêàò P îò òðåõ ïåðåìåííûõ ÿâëÿåòñÿ âñåãäà àïïðîêñè-
ìèðóåìûì òîãäà è òîëüêî òîãäà, êîãäà cP
{ }1 2 3
0
, ,
� .
Åñëè ïðîáëåìà íå âñåãäà àïïðîêñèìèðóåìà, òî îíà àïïðîêñèìàöèîí-
íî-óñòîé÷èâà.
Åñëè ïðîâåðÿþùèé V â PCP-ñèñòåìå èñïîëüçóåò â ñâîåé ðàáîòå k-ìåñòíûé
ïðåäèêàò P äëÿ ïðèíÿòèÿ ðåøåíèÿ, òî áóäåì ñ÷èòàòü, ÷òî òàêîé ïðîâåðÿþùèé
èìååò óñëîâèå ïðèíÿòèÿ P. Ñóùåñòâóåò ñëåäóþùèé êðèòåðèé àïïðîêñèìàöèîí-
íîé óñòîé÷èâîñòè, ñâÿçàííûé ñ PCP-ñèñòåìàìè.
Òåîðåìà 17 [16]. Ïóñòü P k: , ,{ } { }�
1 1 0 1 — ïðåäèêàò è L NP� -ïîëíûé
ÿçûê. Åñëè äëÿ ïðîèçâîëüíîé êîíñòàíòû �� 0 ñóùåñòâóåò ïîëèíîìèàëüíûé ïðî-
âåðÿþùèé â PCP-ñèñòåìå ñ óñëîâèåì ïðèíÿòèÿ P äëÿ L, èñïîëüçóþùèé ëîãàðèô-
ìè÷åñêóþ ñëó÷àéíîñòü è èìåþùèé ïîëíîòó íå ìåíåå 1� � è êîððåêòíîñòü íå áî-
ëåå 2 11� � �k P| ( )| �, òî P àïïðîêñèìàöèîííî-óñòîé÷èâûé.
Äîêàçàòåëüñòâî. Îïðåäåëåíèå ïðèíàäëåæíîñòè ïðîèçâîëüíîãî ýëåìåíòà � ê
L ÿâëÿåòñÿ NP-òðóäíûì. Ïîêàæåì, ÷òî åñëè äëÿ ýêçåìïëÿðà I ïðîáëåìû
Max CSP P� � óäàñòñÿ íàéòè ðåøåíèå ñî çíà÷åíèåì, íå ìåíüøèì
( | ( )| ) ( )2 11� � �k P w I
opt äëÿ ïðîèçâîëüíîé êîíñòàíòû
� 0, òî ìîæíî îïðåäåëèòü
ïðèíàäëåæíîñòü � ê L . Ýòî áóäåò îçíà÷àòü, ÷òî P àïïðîêñèìàöèîííî-óñòîé÷è-
âûé. Ïóñòü � — òàêîå çíà÷åíèå, äëÿ êîòîðîãî
2 1
1
1� � �
�
k P| ( )| �
�
�� �2 11k P| ( )| .
Ïðîâåðÿþùèé èñïîëüçóåò ëîãàðèôìè÷åñêîå ÷èñëî ñëó÷àéíûõ áèò. Çíà÷èò,
ñóùåñòâóåò òîëüêî ïîëèíîìèàëüíîå ÷èñëî âîçìîæíûõ èñõîäîâ. Äëÿ êàæäîãî òà-
êîãî èñõîäà ïðîâåðÿþùèé ñ÷èòûâàåò k áèò ñ äîêàçàòåëüñòâà è ïðîâåðÿåò èõ ñ ïî-
ìîùüþ P. Äîáàâèì ñîîòâåòñòâóþùåå P-îãðàíè÷åíèå ê ýêçåìïëÿðó I ïðîáëåìû
Max CSP P� � . Çàìåòèì, ÷òî âåðîÿòíîñòü òîãî, ÷òî ïðîâåðÿþùèé ïðèìåò äîêàçà-
òåëüñòâî T (T — êîä ïðèïèñûâàíèÿ), â òî÷íîñòè ðàâíà äîëè âûïîëíåííûõ
îãðàíè÷åíèé â ýêçåìïëÿðå I ïðèïèñûâàíèåì, îïðåäåëåííûì T .
Êîððåêòíîñòü PCP-ñèñòåìû îçíà÷àåò, ÷òî åñëè � %L, òî íå ñóùåñòâóåò ïðè-
ïèñûâàíèÿ, êîòîðîå âûïîëíÿåò äîëþ îãðàíè÷åíèé 2 11� � �k P| ( )| � â I . Îäíàêî
åñëè � �L , òî ïðîâåðÿþùèé èìååò ïîëíîòó, êîòîðàÿ ïðåäïîëàãàåò, ÷òî ýêçåì-
ïëÿð I åñòü ( )1� � -âûïîëíåííûì. Òîãäà ñ ïîìîùüþ ÷àñòè ( | ( )| )2 11� � �k P
—
ïðèáëèæåíèÿ ýêçåìïëÿðà I , íàéäåì ðåøåíèå ñî çíà÷åíèåì, íå ìåíüøèì
( | ( )| ) ( ) ( | ( )| )( ) ( )2 1 2 1 11 1� � � �� � � �k kP w I P w I
�opt tot � �� �( | ( )| ) ( )2 11k P w I� tot ,
ãäå w Itot ( ) — îáùèé âåñ âûïîëíåííûõ îãðàíè÷åíèé â I .
Òàêèì îáðàçîì, ìîæíî îïðåäåëèòü, ïðèíàäëåæèò ëè � ê L .
Ïðèìåð 1. Ðàññìîòðèì ïðîáëåìó Max CSP XOR� �3 ñ ñîîòâåòñòâóþùèì ðå-
îïòèìèçàöèîííûì âàðèàíòîì Ins Max CSP XOR� � �3 . Ïî òåîðåìå 7 ïðåäèêàò
XOR — íàñëåäñòâåííî àïïðîêñèìàöèîííî-óñòîé÷èâûé (äîêàçàíî â [16]). Ïðèìå-
íèì òåîðåìó 15 ( , | ( )| )k P� ��3 1 41 è ïîëó÷èì óòâåðæäåíèå.
Óòâåðæäåíèå 1. Äëÿ ïðîáëåìû Ins Max E CSP XOR� � �3 (ðåîïòèìèçàöèÿ
Max E CSP XOR� �3 ) ñóùåñòâóåò ïîëèíîìèàëüíûé ïðèáëèæåííûé àëãîðèòì
ñ îòíîøåíèåì àïïðîêñèìàöèè
2
3
. Äàííîå îòíîøåíèå àïïðîêñèìàöèè ÿâëÿåòñÿ
ïîðîãîâûì.
Ïðèìåð 2. Ðàññìîòðèì ïðîáëåìó Max CSP Q� �3 ñ ñîîòâåòñòâóþùèì ðåîï-
òèìèçàöèîííûì âàðèàíòîì Ins Max CSP Q� � �3 , ãäå Q � � � �1 1 1 1 1 1 1 1( ) ( , , ), ( , , ),{
( , , ), ( , , ), ( , , )� � � � � � �1 1 1 1 1 1 1 1 1 }. Ïðåäèêàò Q — íàñëåäñòâåííî àïïðîêñèìàöèîííî-
óñòîé÷èâûé. Ðàññìîòðèì ñõåìó äîêàçàòåëüñòâà ýòîãî ôàêòà, èñïîëüçóÿ ðåçóëüòà-
òû èç [8].
ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2012, ¹ 1 99
Ïðåäñòàâèì ñõåìó äîêàçàòåëüñòâà íàñëåäñòâåííîé àïïðîêñèìàöèîííîé
óñòîé÷èâîñòè Q. Ðàçëîæåíèå ïðåäèêàòà Q ïî ôîðìóëå Ôóðüå (ïðåäëîæåíèå 1)
èìååò âèä
Q x x x
x x x x x x x x x x x x
( , , )1 2 3
1 2 3 1 2 1 3 2 3 1 2 35 3
8
�
� � � � � � �
. (5)
×òîáû ïîêàçàòü, ÷òî ïðåäèêàò Q àïïðîêñèìàöèîííî-óñòîé÷èâûé, ïðåäñòàâèì
ýôôåêòèâíóþ PCP-ñèñòåìó äëÿ ïðîèçâîëüíîãî NP-òðóäíîãî ÿçûêà ñ óñëîâèåì
ïðèíÿòèÿ Q è çàòåì ïðèìåíèì òåîðåìó 17. Êðàòêî PCP-ñèñòåìà êîíñòðóèðóåò-
ñÿ ñëåäóþùèì îáðàçîì.
1. Ïóñòü ÿçûê L NP� è � �L . PCP-òåîðåìà (òåîðåìà 10) äàåò ïðåîáðàçîâàíèå
òàêîå, ÷òî íà îñíîâàíèè � ïîëó÷àåòñÿ E CNF3� -ôîðìóëà ��,L òàêàÿ, ÷òî åñëè
� �L, òî ��,L âûïîëíèìà; åñëè � %L, òî ��,L — íå áîëåå ÷åì c-âûïîëíèìà äëÿ
êîíñòàíòû c 1 .
2. Ââîäèòñÿ 2P1R-ñèñòåìà ñ ïðîâåðÿþùèì è äâóìÿ ïðóâåðàìè äëÿ ïðîâåðêè
òîãî, ÷òî ôîðìóëà ��,L âûïîëíèìà. Âåðîÿòíîñòü, ÷òî íåâûïîëíèìàÿ ôîðìóëà
ïðèíèìàåòñÿ ïðîâåðÿþùèì, íàçûâàåòñÿ êîððåêòíîñòüþ (soundness). ×òîáû
óìåíüøèòü êîððåêòíîñòü â 2P1R-ñèñòåìå, ïðîâåðÿþùåìó ðàçðåøàåòñÿ çàäàâàòü
îäíîâðåìåííî íåñêîüêî âîïðîñîâ.
3. Êîíñòðóèðóåòñÿ PCP-ñèñòåìà òàêèì îáðàçîì, ÷òî äîêàçàòåëüñòâî T áóäåò
êîäèðîâêîé îòâåòîâ â ïàðàëëåëüíîé 2P1R-ñèñòåìå. Ïðîâåðÿþùèé èñïîëüçóåò íå
áîëåå ëîãàðèôìè÷åñêîå (îò | |� ) ÷èñëî ñëó÷àéíûõ áèò è ïî òðåì áèòîâûì ïîçèöè-
ÿì i j, è k â äîêàçàòåëüñòâå ïðèíèìàåò ðåøåíèå, ÷òî èìååò ìåñòî Q T T Ti j k( , , ) .
×èñëî âîçìîæíûõ òðåõ êîðòåæåé áóäåò ïîëèíîìèàëüíûì îò | |� . Åñëè T — êîä
ïðèïèñûâàíèÿ, êîòîðîå âûïîëíÿåò ��,L, òî ïðîâåðÿþùèé ïðèíèìàåò ðåøåíèå ñ
âåðîÿòíîñòüþ 1� �.
4. Åñëè âåðîÿòíîñòü ïðèíÿòèÿ â PCP-ñèñòåìå íå ìåíåå
5
8
1( )� � , ãäå � — ïðî-
èçâîëüíàÿ ìàëàÿ íåîòðèöàòåëüíàÿ êîíñòàíòà, òî ìîæíî ïðåäñòàâèòü ñòðàòåãèþ
äëÿ ïðóâåðîâ â ïàðàëëåëüíîé 2P1R-ñèñòåìå ñ âåðîÿòíîñòüþ óñïåõà, êîòîðàÿ
áîëüøå, ÷åì êîððåêòíîñòü ñèñòåìû. Èç ýòîãî ñëåäóåò, ÷òî ��,L âûïîëíèìà è
� �L .
Òàêèì îáðàçîì, èìååì 2 1 5 83 1� � �| ( )| /Q , è äàëåå, ïðèìåíÿÿ òåîðåìó 17, ïî-
ëó÷èì, ÷òî ïðåäèêàò Q àïïðîêñèìàöèîííî-óñòîé÷èâûé.
Öåíòðàëüíûì ïîíÿòèåì äëÿ àíàëèçà Ôóðüå áóëåâûõ ôóíêöèé åñòü òàê íàçû-
âàåìûé äëèííûé êîä (long code). Ïóñòü U n U W� �[ ], , ïðè x W� �{ }1 1, | | îáîçíà-
÷èì îãðàíè÷åíèå äëÿ ïåðåìåííûõ, êîòîðûå âñòðå÷àþòñÿ â U , ÷åðåç x U/ . Ïóñòü
FU — ìíîæåñòâî ôóíêöèé f U: , ,| |{ } { }�
�1 1 1 1 . Öåíòðàëüíûé âîïðîñ — èçó÷å-
íèå ôóíêöèé A FU: ,
�{ }1 1 , êàê ìíîæåñòâî âñåõ áóëåâûõ ôóíêöèé îò u U�| | ïå-
ðåìåííûõ (èõ ÷èñëî ñîñòàâëÿåò 22u
).
Îïðåäåëåíèå 16. Äëèííûé êîä ïðèïèñûâàíèÿ x n� �{ }1 1, åñòü îòîáðàæåíèå
A Fx U: ,
�{ }1 1 òàêîå, ÷òî A f f xx ( ) ( )� äëÿ âñåõ f FU� .
Åñëè îòîæäåñòâèòü áóëåâó ôóíêöèþ ñ åå òàáëèöåé èñòèííîñòè, òî äëèííûé
êîä — ýòî ñòðîêà äëèíîé 22u
.
Îïðåäåëåíèå 17. Äëÿ äàííîé ôóíêöèè A FU: ,
�{ }1 1 îïðåäåëèì ôóíêöèþ
Atrue , êîòîðàÿ äëÿ êàæäîé ïàðû ( , )f f� âûáèðàåò îäíó èç äâóõ ôóíêöèé. Åñëè
âûáðàíà f , òî A f A ftrue ( ) ( )� è A f A ftrue ( ) ( )� � � . Åñëè âûáðàíà ôóíêöèÿ � f ,
òî A f A ftrue ( ) ( )� � � è A f A ftrue ( ) ( )� � � .
Èç ýòîãî îïðåäåëåíèÿ ñëåäóåò, ÷òî âñåãäà A f A ftrue true( ) ( )� � � . Îïåðàöèþ
ïîëó÷åíèÿ Atrue èç A íàçûâàþò ñâåðòêîé îòíîñèòåëüíî èñòèíû (folding over true).
Îïðåäåëåíèå 18. Äëÿ ôóíêöèé A FU: ,
�{ }1 1 è h FU� îïðåäåëèì ôóíêöèþ
A Fh U: ,
�{ }1 1 , ïîëîæèâ A f A f hh ( ) ( )� � äëÿ êàæäîé f .
100 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2012, ¹ 1
Îïåðàöèþ ïîëó÷åíèÿ Ah èç A íàçûâàþò óñòàíîâëåíèåì íåîáõîäèìîãî ñî-
ñòîÿíèÿ (conditioning).
 äàëüíåéøåì áóäåò èññëåäîâàíî íåñêîëüêî PCP-ñèñòåì íà îñíîâå àíàëèçà
Ôóðüå ôóíêöèé A.
Íà÷íåì ñ 3-CNF-ôîðìóëû �, ïîëó÷åííîé â ðåçóëüòàòå ïðèìåíåíèÿ òåîðå-
ìû 10 ê ïðîèçâîëüíîìó ÿçûêó L èç NP. Òàêèì îáðàçîì, ëèáî � — âûïîëíèìà,
ëèáî � — íå áîëåå ÷åì c-âûïîëíèìà äëÿ íåêîòîðîé c 1 , è îòëè÷èòü ýòè äâà ñëó-
÷àÿ ïðåäñòàâëÿåòñÿ NP-òðóäíûì. Ïðè÷åì, êàæäàÿ ñêîáêà â � èìååò äëèíó òî÷-
íî 3 è êàæäàÿ ïåðåìåííàÿ ó÷àñòâóåò òî÷íî â ïÿòè ñêîáêàõ.
Áàçîâàÿ 2P1R-ñèñòåìà
Ââîä. Ôîðìóëà � � � � �C C Cm1 2 ... , ãäå C j ñîäåðæèò ïåðåìåííûå
x x xa b cj j j
, , .
Ïðîâåðÿþùèé (Verifier). 1. Ñëó÷àéíî è ðàâíîâåðîÿòíî âûáèðàåò j m�[ ] è
k a b cj j j�{ }, , , j ïîñûëàåòñÿ ê P1, à k ïîñûëàåòñÿ ê P2 .
2. Ïîëó÷àåò çíà÷åíèÿ äëÿ x x xa b cj j j
, , îò P1
è äëÿ xk îò P2 . Ïðèíèìàåò òîãäà
è òîëüêî òîãäà, êîãäà çíà÷åíèÿ äëÿ xk ñîãëàñîâàíû è C j âûïîëíèìà.
Ëåììà 1 [8]. Åñëè � � c-âûïîëíèìà äëÿ ïðîèçâîëüíûõ P1 è P2 , òîVïðèíèìà-
åò ðåøåíèå â áàçîâîé 2P1R-ñèñòåìå ñ âåðîÿòíîñòüþ, íå áîëüøåé
2
3
� c
.
2P1R-ñèñòåìà — u-ïàðàëëåëüíàÿ
Ââîä. Ôîðìóëà � � � � �C C Cm1 2 ... , ãäå C j ñîäåðæèò ïåðåìåííûå
x x xa b cj j j
, , .
Ïðîâåðÿþùèé (Verifier). 1. Äëÿ i u�1 2, , ,� âûáèðàåò ñëó÷àéíî, ðàâíîâåðî-
ÿòíî è íåçàâèñèìî j mi �[ ] è k a b ci j j ji i i
�{ }, , , ïîñûëàåò ( )ji i
n
�1
ê P1, à ( )k i i
n
�1
ïîñûëàåò ê P2 .
2. Ïîëó÷àåò çíà÷åíèÿ äëÿ x x xa b cji ji ji
, , îò Ð
1
è äëÿ xki
îò P2 ïðè i u�1 2, , ,� .
Ïðèíèìàåò ðåøåíèå òîãäà è òîëüêî òîãäà, êîãäà çíà÷åíèÿ äëÿ x
ki
ñîãëàñîâàíû (ñî-
âïàäàþò) è C ji
âûïîëíèìû äëÿ âñåõ 1# #i u. Èñïîëüçóÿ òåîðåìó 11, ëåììó 1 è ïðà-
âèëüíóþ ñòðàòåãèþ, êîãäà � — âûïîëíèìà, ïîëó÷èì ñëåäóþùåå óòâåðæäåíèå.
Ëåììà 2 [8]. Åñëè � åñòü c-âûïîëíèìà, ãäå c 1, òî ñóùåñòâóåò êîíñòàíòà
cc 1 òàêàÿ, ÷òî äëÿ ëþáîãî öåëîãî u îïòèìàëüíûå ñòðàòåãèè äëÿ P1 è P2 îáÿçûâà-
þò V ïðèíÿòü ðåøåíèå (óòâåðäèòü) â 2P1R-ñèñòåìå ñ âåðîÿòíîñòüþ, íå áîëüøåé
cc
u . Åñëè � — âûïîëíèìà, òî V âñåãäà óòâåðæäàåò ðåøåíèå.
Äëÿ ïðîñòîòû îáîçíà÷èì ìíîæåñòâî ïåðåìåííûõ ( )k i i
n
�1
, êîòîðûå ïîñûëàþòñÿ ê
P2 , ÷åðåç U , à ìíîæåñòâî ïåðåìåííûõ ( , , )x x xa b c i
u
ji ji ji �1
, êîòîðûå ïîñûëàþòñÿ ê P1,
÷åðåç W. Ìíîæåñòâî U èìååò u ýëåìåíòîâ, à ìíîæåñòâî W èìååò 3u ýëåìåíòîâ.
 äàëüíåéøåì êîíâåðòèðóåì 2P1R-ñèñòåìó â PCP-ñèñòåìó.
Îïðåäåëåíèå 19. Ñòàíäàðòíî çàïèñàííîå äîêàçàòåëüñòâî ñ ïàðàìåòðîì u
(SWP(u)) ñîñòîèò äëÿ êàæäîãî ìíîæåñòâà V n& [ ] ðàçìåðà íå áîëåå 3u èç ñòðîêè
äëèíîé 22| |
,
V
êîòîðàÿ èíòåðïðåòèðóåòñÿ êàê òàáëèöà ôóíêöèè A FV V: ,
�{ }1 1 .
Îïðåäåëåíèå 20. SWP( )u — êîððåêòíîå äîêàçàòåëüñòâî äëÿ ôîðìóëû � îò n
ïåðåìåííûõ, åñëè ñóùåñòâóåò ïðèïèñûâàíèå x, êîòîðîå âûïîëíÿåò ôóíêöèÿ �
òàê, ÷òî AV — äëèííûé êîä x V/ äëÿ ïðîèçâîëüíîãî V äëèíîé íå áîëåå 3u .
Äëèíà SWP( )u íå áîëåå n u u3 22
3
� , è åñëè u � const, òî äëèíà ïîëèíîìèàëüíà.
ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2012, ¹ 1 101
Òåñò L u
2
� ( )
Ââîä. Çàïèñàííîå äîêàçàòåëüñòâî SWP( )u .
Ñâîéñòâî. Ïðîâåðêà òîãî, ÷òî êîððåêòíîå äîêàçàòåëüñòâî SWP( )u îòíîñèòñÿ
äëÿ äàííîé ôîðìóëû � � � � �C C Cm1 2 ... .
Ïðîâåðÿþùèé. 1. Ñëó÷àéíî è ðàâíîâåðîÿòíî âûáèðàåò ñêîáêè ( )C j i
u
i �1
è
äëÿ êàæäîãî i ñëó÷àéíî è ðàâíîâåðîÿòíî âûáèðàåò ïåðåìåííóþ xki
èç C ji
. Ïóñòü
U x x xk k ku
� { }
1 2
, , ,� , W — ìíîæåñòâî ïåðåìåííûõ, êîòîðûå âñòðå÷àþòñÿ â âû-
áðàííûõ ñêîáêàõ, è h C
i
u
ji
� � �1
.
2. Âûáèðàåò f FV� ðàâíîâåðîÿòíî.
3. Âûáèðàåò g FW1 � ðàâíîâåðîÿòíî.
4. Âûáèðàåò ôóíêöèþ ��FW , ïîëîæèâ �( )y �1 ñ âåðîÿòíîñòüþ 1� � è
�( )y � �1 â ïðîòèâíîì ñëó÷àå, íåçàâèñèìî äëÿ êàæäîãî y W� �{ }1 1, | |.
5. Ôîðìèðóåò g fg2 1� �, ò.å. îïðåäåëÿåò g2 äëÿ êàæäîãî y W� �{ }1 1, | |, êàê
g y f y g y yU2 1( ) ( ) ( ) ( )/� � .
6. Ïðèíèìàåò ðåøåíèå òîãäà è òîëüêî òîãäà, êîãäà Q A f A gU true W h true( ( ), ( ),, , , 1
A gW h true, , ( ))2 1� .
Ëåììà 3. Ïîëíîòà òåñòà L u
2
� ( ) íå ìåíüøå, ÷åì 1� �.
Äîêàçàòåëüñòâî ïîëíîñòüþ àíàëîãè÷íî äîêàçàòåëüñòâó ëåììû 5.1 èç [8].
 äàííîì ñëó÷àå óñëîâèå áîëåå ñèëüíîå è ïîëíîòà íå ìîæåò óìåíüøèòñÿ, ïîýòî-
ìó îíà îñòàåòñÿ íå ìåíüøåé, ÷åì 1� �.
Ðàññìîòðèì òåïåðü êîððåêòíîñòü. Âûðàæåíèå (5) ïðèíèìàåò çíà÷åíèå 1, åñëè
Q x x x( , , )1 2 3 èñòèííî, è 0 â ïðîòèâíîì ñëó÷àå. Òàêèì îáðàçîì, àíàëèçèðóåì ìàòå-
ìàòè÷åñêîå îæèäàíèå (5) ñî çíà÷åíèÿìè x A f x A gU true W h true1 2 1� �, , ,( ), ( ) è
x A gW h true3 2� , , ( ). Ñâåðòêà îòíîñèòåëüíî èñòèíû äàåò E A fU true[ ( )], � 0 äëÿ ñëó-
÷àéíîé ôóíêöèè f , è òàêèì îáðàçîì âñå òåðìû ñòåïåíè 1 â (5) èìåþò îæèäàåìîå
çíà÷åíèå 0. Ïàðû ( , )f g1 è ( , )f g2 ÿâëÿåòñÿ ïàðàìè íåçàâèñèìûõ ôóíêöèé, ïîýòî-
ìó E A f A gU true W h true i[ ( ) ( )], , , � 0 äëÿ i �1 2, . Ïîñêîëüêó òðîéêè ( , , )f g g1 2 è
( , , )� �f g g1 2 âûáèðàþòñÿ òåñòîì ñ îäèíàêîâîé âåðîÿòíîñòüþ, òî
E A g A gW h true W h true[ ( ) ( )], , , ,1 2 0� . Îòñþäà ñëåäóåò, ÷òî åñëè òåñò ïðèíèìàåòñÿ
ñ âåðîÿòíîñòüþ
5
8
� �
, òî èç (5) ïîëó÷èì
E A f A g A gU true W h true W h true[ ( ) ( ) ( )], , , , ,1 2 � �
�.
Îòñþäà, ïîâòîðÿÿ ðàññóæäåíèÿ ïðè äîêàçàòåëüñòâå ëåììû 5.2 èç [8] (â ÷àñò-
íîñòè, î ñóùåñòâîâàíèè óñïåøíûõ ñòðàòåãèé äëÿ P1 è P2 â 2P1R-ñèñòåìå), ïî-
ëó÷èì äîêàçàòåëüñòâî ñëåäóþùåãî óòâåðæäåíèÿ.
Ëåììà 4. Äëÿ ïðîèçâîëüíûõ � �� �0 0, äîïóñòèì, ÷òî âåðîÿòíîñòü òîãî, ÷òî
ïðîâåðÿþùèé ïðèíèìàåò òåñò L u
2
� ( ), åñòü
5
8
� �
. Òîãäà ñóùåñòâóåò ñòðàòåãèÿ äëÿ
P1 è P2 â u-ïàðàëëåëüíîé 2P1R-ñèñòåìå, êîòîðàÿ äàåò âîçìîæíîñòü ïðîâåðÿþùå-
ìó ïðèíÿòü ðåøåíèå ñ âåðîÿòíîñòüþ, íå ìåíüøåé 4
3
2
�
��
�
�
�
�
� .
102 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2012, ¹ 1
Ñîãëàñíî ëåììå 2 èìååì êîððåêòíîñòü 2P1R-ñèñòåìû, ðàâíóþ cc
u . Ïîëîæèâ
4
3
2
�
��
�
�
�
�
� � cc
u , ïîëó÷èì, ÷òî êîððåêòíîñòü PCP-ïðîâåðÿþùåãî íå áîëüøå
5
3
2
8�
�
�
�
�
�
�
�
�
cc
u
�
/ , ÷òî ïðè äîñòàòî÷íî áîëüøèõ u ñòðåìèòñÿ ê 5/8. Ñëåäóåò çàìå-
òèòü, ÷òî 2 1 5 83 1� � �| ( )| /Q . Çàòåì, ïðèìåíÿÿ òåîðåìó 17, ïîëó÷èì, ÷òî Q ÿâëÿåòñÿ
àïïðîêñèìàöèîííî-óñòîé÷èâûì ïðåäèêàòîì.
Íàñëåäñòâåííàÿ àïïðîêñèìàöèîííàÿ óñòîé÷èâîñòü ñëåäóåò èç òîãî ôàêòà,
÷òî âñòàâêà îäíîãî èëè äâóõ íàáîðîâ � � � �� ( , , )1 2 3 â Q íå ìîæåò ïðåîáðàçî-
âàòü â íóëü êîýôôèöèåíò cQ
{ }1 2 3, ,
â ðàçëîæåíèè Ôóðüå Q. Äëÿ ýòîãî ñëåäóåò
ïðèìåíèòü òåîðåìó 16.
Çàìå÷àíèå 2. Çàìåòèì, ÷òî NTW x x x Q x x x( , , ) ( , , )1 2 3 1 2 3� , ò.å. ñîãëàñíî
îïðåäåëåíèþ 2 ïðåäèêàòû NTW è Q èìåþò îäèíàêîâûé òèï. Òàêèì îáðàçîì,
NTW — íàñëåäñòâåííî àïïðîêñèìàöèîííî-óñòîé÷èâûé. Ïðèìåíÿÿ òåîðåìó 15,
ïîëó÷àåì óòâåðæäåíèå 2.
Óòâåðæäåíèå 2. Äëÿ ïðîáëåìû Ins Max E CSP NTW� � �3 (ðåîïòèìèçàöèÿ
Max E CSP NTW� �3 ) ñóùåñòâóåò ïîëèíîìèàëüíûé ïðèáëèæåííûé àëãîðèòì ñ îòíî-
øåíèåì àïïðîêñèìàöèè 8 11/ . Äàííîå îòíîøåíèå àïïðîêñèìàöèè ÿâëÿåòñÿ ïîðîãîâûì.
ÇÀÊËÞ×ÅÍÈÅ
Äëÿ ðåøåíèÿ ïðîáëåìû Ins Max EkCSP P� � � (ðåîïòèìèçàöèÿ Max EkCSP P� � )
ñ àïïðîêñèìàöèîííî-óñòîé÷èâûìè ïðåäèêàòàìè ñóùåñòâóåò ïîëèíîìèàëüíûé ïîðî-
ãîâûé (îïòèìàëüíûé) �( ( ))q P -ïðèáëèæåííûé àëãîðèòì, ãäå �( ( ))
( )
q P
q P
� � �2
1
� � � � � �2 2 2 11d P Pk( ) | ( )| (d P( ) — ïîðîãîâîå «ñëó÷àéíîå» îòíîøåíèå àïïðîê-
ñèìàöèè P). Çàìåòèì, ÷òî ñâîéñòâî àïïðîêñèìàöèîííîé óñòîé÷èâîñòè,
ïî-âèäèìîìó, áîëåå ñèëüíîå, ÷åì ñâîéñòâî NP-ïîëíîòû ñîîòâåòñòâóþùåé ïðî-
áëåìû ðàñïîçíàâàíèÿ, ïîñêîëüêó â äàííîì ñëó÷àå ýôôåêòèâíîå âû÷èñëåíèå íå
ìîæåò äàòü íè÷åãî äðóãîãî, ÷åì ñëó÷àéíîå ïðèïèñûâàíèå çíà÷åíèé èñòèííîñòè
ïåðåìåííûì.
 äàëüíåéøåì áóäóò èññëåäîâàíû âîïðîñû ñóùåñòâîâàíèÿ ðåîïòèìèçàöèîí-
íûõ ïîëèíîìèàëüíûõ ïîðîãîâûõ (îïòèìàëüíûõ) àëãîðèòìîâ äëÿ îáîáùåííûõ
ïðîáëåì î âûïîëíèìîñòè ñ äðóãèìè ïðåäèêàòàìè, îòëè÷íûìè îò àïïðîêñèìàöè-
îííî-óñòîé÷èâûõ.
ÑÏÈÑÎÊ ËÈÒÅÐÀÒÓÐÛ
1. A u s i e l l o G . , E s c o f f i e r B . , M o n n o t J . , P a s c h o s V . T h . Reoptimization of mini-
mum and maximum traveling salesman’s tours // Algorithmic theory. — SWAT 2006, Lect. Notes
Comput. Sci. — Berlin: Springer, 2006. — 4059. — P. 196–207.
2. B o c k e n h a u e r H . J . , F o r l i z z i L . , H r o m k o v i c J . e t a l . On the approximability of
TSP on local modifications of optimal solved instances // Algorithmic Oper. Res. — 2007. — 2(2).
— P. 83–93.
3. B o c k e n h a u e r H . J . , H r o m k o v i c J . , M o m k e T . , W i d m a y e r P . On the hardness of
reoptimization // Proc. of the 34 th Intern. Conf. on Current Trends in Theory and Practice of Com-
puter Science (SOF—SEM 2008); Lect. Notes Comput. Sci. — Berlin: Springer, 2008. — 4910. —
P. 50–65.
4. E s c o f f i e r B . , M i l a n i c M . , P a s c h o s V . Simple and fast reoptimizations for the Steiner
tree problem // Algorithmic Operations Research. — 2009. — 4(2). — P. 86–94.
ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2012, ¹ 1 103
5. A r c h e t t i C . , B e r t a z z i L . , S p e r a n z a M . G . Reoptimizing the travelling salesman prob-
lem // Networks. — 2003. — 42(3). — P. 154–159.
6. A r c h e t t i C . , B e r t a z z i L . , S p e r a n z a M . G . Reoptimizing the 0-1 knapsack problem //
Discrete Applied Mathematics. — 2010. — 158 (17). — P. 1879–1887.
7. A u s i e l l o G . , B o n i f a c i V . , E s c o f f i e r B . Complexity and approximation in
reoptimization // Computability in Context: Computation and Logic in the Real World (Åds. S. Barry
Cooper and Andrea Sorbi). — 2011. — London: Imperial College Press. — P. 101–130.
8. H a s t a d J . Some optimal inapproximability results // J. of the ACM. — 2001. — 48, N 4. —
P. 798–859.
9. H a s t a d J . Complexity theory, proofs and approximation // European Congress of Mathematics
(Ed. A. Laptev, European Mathematical Society).— Stockholm, Sweden, 2005.
10. H a s t a d J . On the efficient approximability of constraint satisfaction problems // Surveys in
Combinatorics 2007. — London Mathematical Society Lecture Notes Series (Eds. A. Hilton and
J. Talbot). — Cambridge: University Press. — 2007. — 346. — P. 201–222.
11. F e i g e U . A threshold of ln n for approximating set cover // J. of the ACM. — 1998. — 45, N 4.
— P. 634–652.
12. A r o r a S . , L u n d C . , M o t w a n i R . , S u d a n M . , S z e g e d y M . Proof verification and
intractability of approximation problems // J. of the ACM. — 1998. — 45, N 3. — P. 501–555.
13. G o l d r e i c h O . , G o l d w a s s e r S . , R o n D . Property testing and its connection to learning
and approximation abstract // J. of the ACM. — 1998. — 45, N 4. — P. 653–750.
14. G o l d r e i c h O . , S u d a n M . Locally testable codes and PCPs of almost-linear length // J. of the
ACM. — 2006. — 53, N 4. — P. 558–655.
15. G o e m a n s M . X . , W i l l i a m s o n D . P . Improved approximation algorithms for maximum cut
and satisfiability problems using semidefinite programming // J. of the ACM. — 1995. — 42. —
P. 1115–1145.
16. H a s t G . Beating a random assignment. — Doctoral Thesis. — Royal Institute of Technology. —
Stockholm, Sweden, 2005.
17. Z w i c k U . Approximation algorithms for constraint satisfaction problems involving at most three
variables per constraint // Proceedings of the 9-th Annual ACM — SIAM Symposium on Discrete
Algorithms, 1998. — P. 551–560.
18. O ’ D o n n e l R . Some topics in analysis of Boolean functions // Electronic Colloquium on Compu-
tational Complexity, 2008. — Report No. 55.
19. K h o t S . Inapproximability of NP-complete problems, discrete Fourier analysis, and geometry //
Proceedings of the International Congress of Mathematicians. — 2010. — Hyderabad, India.
20. R a z R . A parallel repetition theorem // SIAM J. on Computing. — 1998. — 27, N 3. —
P. 763–803.
21. V a z i r a n i V . V . Approximation algorithms. — Berlin: Springer, 2001. — 380 p.
22. Ì è õ à é ë þ ê Â . À . Îáùèé ïîäõîä ê îöåíêå ñëîæíîñòè ïîñòîïòèìàëüíîãî àíàëèçà
äèñêðåòíûõ çàäà÷ îïòèìèçàöèè // Êèáåðíåòèêà è ñèñòåìíûé àíàëèç. — 2010. — 46, ¹ 2. —
Ñ. 134–141.
23. Ì è õ à é ë þ ê  . À . Ðåîïòèìèçàöèÿ çàäà÷è î ïîêðûòèè ìíîæåñòâàìè // Òàì æå. — 2010. —
46, ¹ 6. — Ñ. 27–31.
Ïîñòóïèëà 12.05.2011
104 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2012, ¹ 1
|
| id | nasplib_isofts_kiev_ua-123456789-84019 |
| institution | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| issn | 0023-1274 |
| language | Russian |
| last_indexed | 2025-11-29T10:20:56Z |
| publishDate | 2012 |
| publisher | Інститут кібернетики ім. В.М. Глушкова НАН України |
| record_format | dspace |
| spelling | Михайлюк, В.А. Сергиенко, И.В. 2015-07-02T08:13:39Z 2015-07-02T08:13:39Z 2012 Реоптимизация обобщенных проблем о выполнимости с аппроксимационно-устойчивыми предикатами / В.А. Михайлюк, И.В. Сергиенко // Кибернетика и системный анализ. — 2012. — Т. 48, № 1. — С. 89-104. — Бібліогр.: 23 назв. — рос. 0023-1274 https://nasplib.isofts.kiev.ua/handle/123456789/84019 519.854 Якщо k=O(logn) і предикат P спадково апроксимаційно-стійкий для реоптимізації проблеми Max-EkCSP-P, при вставці нового істинісного значення в предикат і деякого обмеження існує поліноміальний наближений алгоритм з відношенням апроксимації, яке є пороговим. If k=O(logn) and a predicate Р is approximation resistant for the reoptimization of problem Max-EkCSP-P under insertion of a truth-value in the predicate and some constraint, then there exists a polynomial algorithm with the approximation ratio that is threshold ru Інститут кібернетики ім. В.М. Глушкова НАН України Кибернетика и системный анализ Кибернетика Реоптимизация обобщенных проблем о выполнимости с аппроксимационно-устойчивыми предикатами Реоптимізація узагальнених проблем про виконуваність з апроксимаційно-стійкими предикатами Reoptimization of constraint satisfaction problems with approximation resistant predicates Article published earlier |
| spellingShingle | Реоптимизация обобщенных проблем о выполнимости с аппроксимационно-устойчивыми предикатами Михайлюк, В.А. Сергиенко, И.В. Кибернетика |
| title | Реоптимизация обобщенных проблем о выполнимости с аппроксимационно-устойчивыми предикатами |
| title_alt | Реоптимізація узагальнених проблем про виконуваність з апроксимаційно-стійкими предикатами Reoptimization of constraint satisfaction problems with approximation resistant predicates |
| title_full | Реоптимизация обобщенных проблем о выполнимости с аппроксимационно-устойчивыми предикатами |
| title_fullStr | Реоптимизация обобщенных проблем о выполнимости с аппроксимационно-устойчивыми предикатами |
| title_full_unstemmed | Реоптимизация обобщенных проблем о выполнимости с аппроксимационно-устойчивыми предикатами |
| title_short | Реоптимизация обобщенных проблем о выполнимости с аппроксимационно-устойчивыми предикатами |
| title_sort | реоптимизация обобщенных проблем о выполнимости с аппроксимационно-устойчивыми предикатами |
| topic | Кибернетика |
| topic_facet | Кибернетика |
| url | https://nasplib.isofts.kiev.ua/handle/123456789/84019 |
| work_keys_str_mv | AT mihailûkva reoptimizaciâobobŝennyhproblemovypolnimostisapproksimacionnoustoičivymipredikatami AT sergienkoiv reoptimizaciâobobŝennyhproblemovypolnimostisapproksimacionnoustoičivymipredikatami AT mihailûkva reoptimízacíâuzagalʹnenihproblemprovikonuvanístʹzaproksimacíinostíikimipredikatami AT sergienkoiv reoptimízacíâuzagalʹnenihproblemprovikonuvanístʹzaproksimacíinostíikimipredikatami AT mihailûkva reoptimizationofconstraintsatisfactionproblemswithapproximationresistantpredicates AT sergienkoiv reoptimizationofconstraintsatisfactionproblemswithapproximationresistantpredicates |