PLS (күрделілігі) - PLS (complexity)

Жылы есептеу күрделілігі теориясы, Жергілікті полиномдық іздеу (PLS) Бұл күрделілік сыныбы а. табу қиындығын модельдейді жергілікті оңтайлы шешімі оңтайландыру мәселесі. PLS-тегі проблемалардың негізгі сипаттамалары - шешім құнын есептеуге болады көпмүшелік уақыт және ерітіндінің маңын полиномдық уақытта іздеуге болады. Сондықтан шешімнің полиномдық уақыттағы жергілікті оптимум болып табылатындығын немесе болмайтындығын тексеруге болады, сонымен қатар, мәселе мен мәселені шешу үшін қолданылатын алгоритмге байланысты глобальды оптимумның орнына жергілікті оптимумды табу жылдамырақ болуы мүмкін .

Сипаттама

Жергілікті оптимумды іздеу кезінде екі қызықты мәселе шешілуі керек: Біріншіден, жергілікті оптимумды қалай табуға болады, ал екіншіден, жергілікті оптимумды табу үшін қанша уақыт қажет. Көптеген жергілікті іздеу алгоритмдері үшін олар полиномдық уақытта жергілікті оптимумды таба ала ма, жоқ па белгісіз.^[1] Сонымен, Джонсон, Пападимитрио және Яннакакис деген жергілікті оптимумды табу қанша уақыт алады деген сұраққа жауап беру үшін ^[2] өзінің жұмысына PLS күрделілік класын енгізді «Жергілікті іздеу қаншалықты оңай». Онда жергілікті оңтайлылықты полиномдық уақытта тексеруге болатын жергілікті іздеу проблемалары бар.

Жергілікті іздеу проблемасы, егер келесі қасиеттер қанағаттандырылса:

• Әрбір шешімнің мөлшері дананың өлшемінде көпмүшелікпен шектелген ${displaystyle I}$.
• Көпмүшелік уақытта проблемалық дананың бірнеше шешімін табуға болады.
• Әрбір шешімнің құнын полиномдық уақытта есептеуге болады.
• Көпмүшелік уақытта әр шешімнің барлық көршілерін табуға болады.

Осы қасиеттердің көмегімен әр шешімді табуға болады ${displaystyle s}$ ең жақсы көрші шешім немесе егер ондай жақсы көршілес шешім болмаса, мұны айтыңыз ${displaystyle s}$ жергілікті оптимум.

Мысал

Келесі мысалды қарастырайық ${displaystyle I}$ туралы Max-2Sat Мәселе: ${displaystyle (x_ {1} vee x_ ​​{2}) сына (мысалы, x_ {1} vee x_ ​​{3}) сына (мысалы, x_ {2} vee x_ ​​{3})}$. Мақсат - қанағаттандырылған сөйлемдердің қосындысын көбейтетін тапсырма табу.

A шешім ${displaystyle s}$ бұл үшін әрқайсысын беретін бит жолы ${displaystyle x_ {i}}$ мәні 0 немесе 1. Бұл жағдайда шешім, мысалы, 3 биттен тұрады ${displaystyle s = 000}$, бұл тағайындауды білдіреді ${displaystyle x_ {1}}$ дейін ${displaystyle x_ {3}}$ 0. мәнімен. Шешімдер жиынтығы ${displaystyle F_ {L} (I)}$ барлық мүмкін тапсырмалардың жиынтығы болып табылады ${displaystyle x_ {1}}$, ${displaystyle x_ {2}}$ және ${displaystyle x_ {3}}$.

The құны әрбір шешім - бұл қанағаттандырылған сөйлемдердің саны, сондықтан ${displaystyle c_ {L} (I, s = 000) = 2}$ өйткені екінші және үшінші тармақ қанағаттандырылды.

Флип-көрші шешім ${displaystyle s}$ бит жолының бір битін айналдыру арқылы жетеді ${displaystyle s}$, сондықтан көршілері ${displaystyle s}$ болып табылады ${displaystyle N (I, 000) = {100,010,001}}$ келесі шығындармен:

${displaystyle c_ {L} (I, 100) = 2}$

${displaystyle c_ {L} (I, 010) = 2}$

${displaystyle c_ {L} (I, 001) = 2}$

Шығындары жақсы көршілер жоқ ${displaystyle s}$, егер біз максималды шығындармен шешім іздесек. Сөйтсе де ${displaystyle s}$ бұл жаһандық оптимум емес (мысалы, шешім болар еді) ${displaystyle s '= 111}$ барлық тармақтарды қанағаттандырады және бар ${displaystyle c_ {L} (I, s ') = 3}$), ${displaystyle s}$ жергілікті оптимум болып табылады, өйткені көршілерінің ешқайсысы жақсы шығындарға ие емес.

Интуитивті түрде бұл проблема деп айтуға болады PLS-те жатыр, өйткені:

• Көпмүшелік уақытта дананың шешімін табуға болады, мысалы, барлық биттерді 0-ге қою арқылы.
• Шешімнің құнын полиномдық уақыт ішінде бүкіл инстанцияны бір рет өтіп, қанағаттандырылған сөйлемдерді санау арқылы есептеуге болады.
• Әр түрлі шешімдер жиынтығын алу арқылы полиномдық уақытта шешімнің барлық көршілерін табуға болады ${displaystyle s}$ дәл бір бит.

Ресми анықтама

Жергілікті іздеу проблемасы ${displaystyle L}$ жиынтығы бар ${displaystyle D_ {L}}$ кодталған даналар жіптер ақырлы алфавит ${displaystyle Sigma}$. Әр дана үшін ${displaystyle I}$ ақырғы шешім жиынтығы бар ${displaystyle F_ {L} (I)}$. Келіңіздер ${displaystyle R}$ модельдейтін қатынас болуы керек ${displaystyle L}$. Қатынас ${displaystyle Rsubseteq D_ {L} imes F_ {L} (I): = {(I, s) Iin D_ {L}, sin F_ {L} (I)}}$ ішінде PLS ^{[2] [3][4]} егер:

• Әрбір шешімнің мөлшері ${displaystyle sin F_ {L} (I)}$ өлшемімен шектелген көпмүшелік болып табылады ${displaystyle I}$
• Проблемалық даналар ${displaystyle Iin D_ {L}}$ және шешімдер ${displaystyle sin F_ {L} (I)}$ көпмүшелік уақыт тексерілуі мүмкін
• Уақытты есептейтін көпмүшелік функция бар ${displaystyle A: D_ {L} мылтық F_ {L} (I)}$ әр данасы үшін қайтарылады ${displaystyle Iin D_ {L}}$ кейбір шешім ${displaystyle sin F_ {L} (I)}$
• Уақытты есептейтін көпмүшелік функция бар ${displaystyle B: D_ {L} imes F_ {L} (I) ightarrow mathbb {R} ^ {+}}$ ^[5] бұл әрбір шешім үшін қайтарылады ${displaystyle sin F_ {L} (I)}$ дананың ${displaystyle Iin D_ {L}}$ баға ${displaystyle c_ {L} (I, s)}$
• Уақытты есептейтін көпмүшелік функция бар ${displaystyle N: D_ {L} imes F_ {L} (I) ightarrow Powerset (F_ {L} (I))})$ бұл даналар шешімінің жұбы үшін көршілер жиынтығын қайтарады
• Уақытты есептейтін көпмүшелік функция бар ${displaystyle C: D_ {L} imes F_ {L} (I) enarrow N (I, s) cup {OPT}}$ бұл көрші шешімді қайтарады ${displaystyle s}$ шешімнен гөрі жақсы шығындармен ${displaystyle s}$, немесе бұл туралы айтады ${displaystyle s}$ жергілікті деңгейде оңтайлы болып табылады
• Әрбір инстанция үшін ${displaystyle Iin D_ {L}}$, ${displaystyle R}$ дәл жұптарды қамтиды ${displaystyle (I, s)}$ қайда ${displaystyle s}$ жергілікті оңтайлы шешімі болып табылады ${displaystyle I}$

Дана ${displaystyle D_ {L}}$ құрылымы бар жасырын график (деп те аталады Өтпелі график ^[6]), шыңдар екі шешімді шешімдер болып табылады ${displaystyle s, s'in F_ {L} (I)}$ iff бағытталған доға арқылы қосылған ${displaystyle s'in N (I, s)}$.

A жергілікті оңтайлы шешім болып табылады ${displaystyle s}$, жақсы шығысы бар көршісі жоқ. Жасырын графикте локальды оптимум - раковина. Әрбір жергілікті оптимум a болатын көршілік жаһандық оңтайлы, бұл ең жақсы шығындармен шешім болып табылады, деп аталады дәл көршілік.^[6][1]

Мысал құрылымдары

Логикалық айнымалылармен (немесе биттік жолдармен) проблемаларға арналған көршілес құрылымдардың мысалы:

• Флип^[2] - Шешімнің маңайы ${displaystyle s = x_ {1}, ..., x_ {n}}$ бір ерікті енгізу битін жоққа шығару (айналдыру) арқылы қол жеткізуге болады ${displaystyle x_ {i}}$. Сондықтан бір шешім ${displaystyle s}$ және оның барлық көршілері ${displaystyle rin N (I, s)}$ бар Хамминг қашықтығы бір: ${displaystyle H (s, r) = 1}$.
• Керниган-Лин^[2][6] - шешім ${displaystyle r}$ шешімнің көршісі болып табылады ${displaystyle s}$ егер ${displaystyle r}$ -дан алуға болады ${displaystyle s}$ бірде-бір рет екі рет айналдырылмайтын ашкөздіктер тізбегі бойынша. Бұл дегеніміз, басталады ${displaystyle s}$, Флип- көрші ${displaystyle s_ {1}}$ туралы ${displaystyle s}$ ең жақсы шығындармен немесе шығындардың ең аз шығындарымен Керниган-Лин құрылымындағы көршілер ретінде таңдалады. Сондай-ақ ең жақсы (немесе нашар) көрші ${displaystyle s_ {1}}$ және т.б., дейін ${displaystyle s_ {i}}$ - бұл шешім ${displaystyle s}$ жоққа шығарылды. Егер бір рет аударылған болса, сәл артқа аударуға жол берілмейтінін ескеріңіз.
• k-аудару^[7] - шешім ${displaystyle r}$ шешімнің көршісі болып табылады ${displaystyle s}$ егер Хамминг қашықтығы ${displaystyle H}$ арасында ${displaystyle s}$ және ${displaystyle r}$ ең көп дегенде ${displaystyle k}$, сондықтан ${displaystyle H (s, r) leq k}$.

Графиктердегі проблемаларға арналған көршілес құрылымдардың мысалы:

• Ауыстыру^[8] - Бөлім ${displaystyle (P_ {2}, P_ {3})}$ Графиктегі түйіндер бөлімнің көршісі болып табылады ${displaystyle (P_ {0}, P_ {1})}$ егер ${displaystyle (P_ {2}, P_ {3})}$ -дан алуға болады ${displaystyle (P_ {0}, P_ {1})}$ бір түйінді ауыстыру арқылы ${displaystyle p_ {0} P_ {0}}$ түйінмен ${displaystyle p_ {1} P_ {1}} ішінде$.
• Керниган-Лин^[1][2] - бөлім ${displaystyle (P_ {2}, P_ {3})}$ көршісі болып табылады ${displaystyle (P_ {0}, P_ {1})}$ егер ${displaystyle (P_ {2}, P_ {3})}$ түйіндеріндегі своптардың ашкөздік дәйектілігі арқылы алуға болады ${displaystyle P_ {0}}$ түйіндері бар ${displaystyle P_ {1}}$. Бұл екі түйінді білдіреді ${displaystyle p_ {0} P_ {0}}$ және ${displaystyle p_ {1} P_ {1}} ішінде$ ауыстырылады, онда бөлім ${displaystyle ((P_ {0} setminus p_ {0}) кубок p1, (P_ {1} setminus p_ {1}) кубок p_ {0})}$ ең жоғары салмақты алады немесе ең аз салмақты жоғалтады. Ешқандай түйінді екі рет ауыстыруға жол берілмейтінін ескеріңіз.
• Фидучиа-Матейз ^[1][9] - Бұл көршілестік Керниган-Линнің көршілес құрылымына ұқсас, бұл айырбастың ашкөздік дәйектілігі, тек әр своп екі сатыда болатындығынан. Біріншіден ${displaystyle p_ {0} P_ {0}}$ шығындардың ең көп пайдасы немесе шығындардың ең аз шығындарымен ауыстырылады ${displaystyle P_ {1}}$, содан кейін түйін ${displaystyle p_ {1} P_ {1}} ішінде$ ең көп шығындармен немесе шығындардың ең аз шығындарымен ауыстырылады ${displaystyle P_ {0}}$ бөлімдерді қайтадан теңестіру үшін. Тәжірибелер көрсеткендей, Фидучиа-Маттейздің стандартты алгоритмнің әр қайталануында жұмыс уақыты аз болады, дегенмен ол кейде төменгі жергілікті оптимумды табады.
• FM-ауыстыру^[1] - Бұл көршілес құрылым Фидучия-Маттейз көршілік құрылымына негізделген. Әр шешім ${displaystyle s = (P_ {0}, P_ {1})}$ бір ғана көршісі бар, Фидучиа-Маттейздің алғашқы своптан кейін алынған бөлімі.

Стандартты алгоритм

Келесі есептеу мәселесін қарастырыңыз:Кейбір мысал келтірілген ${displaystyle I}$ PLS проблемасы ${displaystyle L}$, жергілікті оңтайлы шешімді табыңыз ${displaystyle sin F_ {L} (I)}$ осындай ${displaystyle c_ {L} (I, s ') geq c_ {L} (I, s)}$ барлығына ${displaystyle s'in N (I, s)}$.

Кез-келген жергілікті іздеу мәселесін келесі қайталанатын жетілдіру алгоритмінің көмегімен шешуге болады:^[2]

1. Пайдаланыңыз ${displaystyle A_ {L}}$ бастапқы шешімді табу ${displaystyle s}$
2. Алгоритмді қолданыңыз ${displaystyle C_ {L}}$ жақсы шешім табу ${displaystyle s'in N (I, s)}$. Егер мұндай шешім болса, ауыстырыңыз ${displaystyle s}$ арқылы ${displaystyle s}$ және 2-қадамды қайталаңыз, әйтпесе оралыңыз ${displaystyle s}$

Өкінішке орай, мәселе оңтайлы болса да, оны жақсарту үшін экспоненциалды қадамдар қажет ${displaystyle L}$ дәл көпмүшелік уақытта шешілуі мүмкін.^[2] Стандартты алгоритмді әрдайым қолдану қажет емес, белгілі бір мәселе үшін басқаша, жылдам алгоритм болуы мүмкін. Мысалы үшін қолданылған жергілікті іздеу алгоритмі Сызықтық бағдарламалау болып табылады Қарапайым алгоритм.

Стандартты алгоритмнің жұмыс уақыты болып табылады жалған полином шешімнің әртүрлі шығындарының санында.^[10]

Стандартты алгоритмге қажет кеңістік тек көпмүшелік. Бұл тек ағымдағы шешімді сақтау керек ${displaystyle s}$, бұл анықтамамен шектелген көпмүшелік.^[1]

Қысқартулар

A Қысқарту бір мәселенің екінші мәселеге, екінші есептің, кем дегенде, біріншіге қарағанда қиын екенін көрсету үшін қолданылуы мүмкін. Атап айтқанда, PLS-ті азайту, PLS-тегі жергілікті іздеу проблемасының PLS-пен аяқталғанын дәлелдеу үшін, PLS-мен аяқталған мәселені PLS-мен аяқталғанға дейін азайту арқылы қолданылады.

PLS-төмендету

Жергілікті іздеу проблемасы ${displaystyle L_ {1}}$ PLS-төмендетуге болады^[2] жергілікті іздеу проблемасына ${displaystyle L_ {2}}$ егер екі полиномдық уақыт функциясы болса ${displaystyle f: D_ {1} ightarrow D_ {2}}$ және ${displaystyle g: D_ {1} imes F_ {2} (f (I_ {1})) Fightarrow F_ {1} (I_ {1})}$ осылай:

• егер ${displaystyle I_ {1}}$ данасы болып табылады ${displaystyle L_ {1}}$ , содан кейін ${displaystyle f (I_ {1})}$ данасы болып табылады ${displaystyle L_ {2}}$
• егер ${displaystyle s_ {2}}$ шешімі болып табылады ${displaystyle f (I_ {1})}$ туралы ${displaystyle L_ {2}}$ , содан кейін ${displaystyle g (I_ {1}, s_ {2})}$ шешімі болып табылады ${displaystyle I_ {1}}$ туралы ${displaystyle L_ {1}}$
• егер ${displaystyle s_ {2}}$ мысалы, жергілікті оптимум ${displaystyle f (I_ {1})}$ туралы ${displaystyle L_ {2}}$ , содан кейін ${displaystyle g (I_ {1}, s_ {2})}$ мысалы, жергілікті оптимум болуы керек ${displaystyle I_ {1}}$ туралы ${displaystyle L_ {1}}$

Тек жергілікті оптиманы картаға түсіру жеткілікті ${displaystyle f (I_ {1})}$ жергілікті оптимумға дейін ${displaystyle I_ {1}}$және барлық басқа шешімдерді салыстыру, мысалы, қайтарылған стандартты шешімге ${displaystyle A_ {1}}$.^[6]

PLS-төмендету болып табылады өтпелі.^[2]

PLS-тің қысқаруы

Анықтаманың ауысу графигі

Өтпелі график^[6] ${displaystyle T_ {I}}$ дананың ${displaystyle I}$ ақаулық ${displaystyle L}$ бағытталған граф. Түйіндер шешімдер жиынтығының барлық элементтерін ұсынады ${displaystyle F_ {L} (I)}$ және шеттері бір шешімнен көршісіне жақсырақ жақсы бағамен бағытталады. Сондықтан бұл ациклдік график. Шұңқыр - шығыс жиектері жоқ түйін, жергілікті оңтайлы болып табылады ${displaystyle v}$ - бастап ең қысқа жолдың ұзындығы ${displaystyle v}$ Өтпелі графиктің биіктігі барлық төбелердің биіктігінің ең үлкені, сондықтан бұл түйіннен ең жақын раковинаға дейінгі ең қысқа жолдың биіктігі.

Тығыз PLS-қысқарту анықтамасы

PLS-төмендету ${displaystyle (f, g)}$ жергілікті іздеу проблемасынан ${displaystyle L_ {1}}$ жергілікті іздеу проблемасына ${displaystyle L_ {2}}$ Бұлқатаң PLS-төмендету^[8] егер кез-келген дана болса ${displaystyle I_ {1}}$ туралы ${displaystyle L_ {1}}$, ішкі жиын ${displaystyle R}$ дананың шешімі ${displaystyle I_ {2} = f (I_ {1})}$ туралы ${displaystyle L_ {2}}$ келесі қасиеттерді қанағаттандыру үшін таңдауға болады:

• ${displaystyle R}$ басқа шешімдермен қатар, барлық жергілікті оптималарды қамтиды ${displaystyle I_ {2}}$
• Әрбір шешім үшін ${displaystyle p}$ туралы ${displaystyle I_ {1}}$ , шешім ${displaystyle qin R}$ туралы ${displaystyle I_ {2} = f (I_ {1})}$ көпмүшелік уақытта құруға болады, осылайша ${displaystyle g (I_ {1}, q) = p}$
• Егер өтпелі график болса ${displaystyle T_ {f (I_ {1})}}$ туралы ${displaystyle f (I_ {1})}$ бастап тікелей жолды қамтиды ${displaystyle q}$ дейін ${displaystyle q_ {0}}$, және ${displaystyle q, q_ {0} in R}$, бірақ барлық ішкі жол шыңдары сыртта ${displaystyle R}$, содан кейін тиісті шешімдер үшін ${displaystyle p = g (I_ {1}, q)}$ және ${displaystyle p_ {0} = g (I_ {1}, q_ {0})}$ екеуін де ұстайды ${displaystyle p = p_ {0}}$ немесе ${displaystyle T_ {I_ {1}}}$ шетінен тұрады ${displaystyle p}$ дейін ${displaystyle p_ {0}}$

Басқа күрделілік кластарымен байланыс

PLS функционалды нұсқаларының арасында орналасқан P және NP: ФП ⊆ PLS ⊆ FNP.^[2]

PLS сонымен қатар TFNP,^[11] шешімі бар екендігі кепілдендірілген және полиномдық уақытта танылатын есептеу есептерін сипаттайтын. PLS-тегі проблема үшін шешімнің болуы кепілдендірілген, өйткені бүкіл графиктің минималды шыңдары дұрыс шешім болып табылады және шешімнің дұрыстығын көршілерін есептеу және әрқайсысының шығындарын басқасымен салыстыру арқылы тексеруге болады.

Егер PLS проблемасы болса, бұл дәлелденген NP-hard, онда NP = co-NP.^[2]

PLS-толықтығы

Анықтама

Жергілікті іздеу проблемасы ${displaystyle L}$ PLS аяқталған,^[2] егер

• ${displaystyle L}$ PLS тізімінде
• PLS-тегі барлық проблемалар PLS-ке дейін азайтылуы мүмкін ${displaystyle L}$

Оңтайландыру нұсқасы тізбек астында проблема Флип көршілік құрылымы PLS-пен аяқталған бірінші мәселе екендігі көрсетілген.^[2]

PLS аяқталған мәселелер тізімі

Бұл PLS аяқталған кейбір белгілі мәселелердің толық емес тізімі.

PLS-ге толық есептер және олардың бір-біріне қалай азаятындығы туралы шолу. Синтаксис: Оңтайландыру-проблема / көршілік құрылымы. Нүктелі көрсеткі: Ақаулықтан PLS-азайту ${displaystyle L}$ проблемаға ${displaystyle Q: Lleftarrow Q}$. Қара көрсеткі: PLS-тің қысқаруы.^[4]

Ескерту: проблема / көршілік құрылым

• Min / Max-circuit / Flip PLS-мен аяқталған бірінші мәселе екендігі дәлелденді.^[2]
• Оң-барлығы-тең емес-max-3Sat / Flip PLS-ті Min / Max-circuit / Flip-тен Positive-not-all-teng-max-3Sat / Flip-ге дейін қатаң PLS-төмендету арқылы дәлелдеді. Positive-all-teng-max-3Sat / Flip мәнін Max-Cut / Flip-тен де азайтуға болатындығын ескеріңіз.^[8]
• Барлығы бірдей емес-оң-max-3Sat / Kernighan-Lin PLS-ті Min / Max-circuit / Flip-тен Positive-all-not-all-teng-max-3Sat / Kernighan-Lin-ге қатаң төмендету арқылы толықтай дәлелденді.^[1]
• Max-2Sat / Аудару Max-Cut / Flip-тен Max-2Sat / Flip-ге дейін қатты PLS-төмендету арқылы PLS-толық екендігі дәлелденді.^[1][8]
• Min-4Sat-B / Аудару PLS-толық екендігі дәлелденді, ол Min-circuit / Flip-тен Min-4Sat-B / Flip-ге дейін қатты PLS-төмендету арқылы.^[7]
• Max-4Sat-B / Flip(немесе CNF-SAT) PLS-толық Max-circuit / Flip-тен Max-4Sat-B / Flip-ге дейін PLS-төмендету арқылы дәлелденді.^[12]
• Max-4Sat- (B = 3) / Flip Max-circuit / Flip-тен Max-4Sat- (B = 3) / Flip-ке дейін PLS-төмендету арқылы PLS-толық екендігі дәлелденді.^[13]
• Max-Uniform-Graph-Partitioning / Ауыстыру Max-Cut / Flip-тен Max-Uniform-Graph-partitioning / Swap-ге дейін қатты PLS-төмендету арқылы PLS-толық екендігі дәлелденді.^[8]
• Максималды-бірыңғай-графикалық бөлу / Фидучиа-Матейз дәлелсіз PLS-толық деп көрсетілген.^[1]
• Максималды-бірыңғай-графикалық бөлу / FM-ауыстыру Max-Cut / Flip-тен Max-Uniform-Graph-partitioning / FM-Swap-ге дейін қатты PLS-қысқарту арқылы PLS-толық екендігі дәлелденді.^[8]
• Max-Uniform-Graph-Partitioning / Керниган-Лин PLS-толық Min-Max-circuit / Flip-тен Max-Uniform-Graph-Partitioning / Kernighan-Lin-ге дейін PLS-төмендету арқылы дәлелденген.^[2] Positive-all-not-max-3Sat / Kernighan-Lin-ден Max-Uniform-Graph-Partitioning / Kernighan-Lin-ге дейін қатты PLS-қысқарту бар.^[1]
• Max-Cut / Аудару PLS-толық екендігі Positive-all-teng-max-3Sat / Flip-тен Max-Cut / Flip-ге дейін қатты PLS-төмендету арқылы дәлелденді.^[1][8]
• Max-Cut / Керниган-Лин дәлелдемесіз PLS-толық деп талап етіледі.^[6]
• Min-Тәуелсіз-Доминант-Set-B / k-Flip PLS-толық Min-4Sat-B ’/ Flip-тен Min-Тәуелсіз-Доминантты-Set-B / k-Flip-ге дейін қысқарту арқылы толықтай дәлелденді.^[7]
• Салмақ-тәуелсіз жиынтық / Өзгерту дәлелдемесіз PLS-толық деп талап етіледі.^[2][8][6]
• Қасиеті бар максималды-салмақталған-регистр-өзгеріс / өзгеріс PLS-ге тең, егер P = ”қасиетінің шеттері болмаса”, өйткені ол Weighted-Independent-Set / Change-ге тең. Ол жалпы тұқым қуалайтын, тривиальды емес P қасиеті үшін PLS-толық екендігі дәлелденген, ол салмақты-тәуелсіз-жиынтықтан / өзгертуден максималды-салмақталған-субграфқа-меншіктен-өзгертілгенге дейін қатты PLS-төмендету арқылы.^[14]
• Қақпақ / k-өзгеріс (3, 2, r) -Max-Contraint-Assignment / Change-Set-Cover / k-өзгертуге дейін PLS-тің қысқаруы арқылы әрбір k complete 2 үшін PLS-толық екендігі дәлелденді.^[15]
• Metric-TSP / k-өзгерту Max-4Sat-B / Flip-тен Metric-TSP / k-Change-қа дейін PLS-төмендету арқылы PLS-толық екендігі дәлелденді.^[13]
• Metric-TSP / Лин-Керниган Max-2Sat / Flip-тен Metric-TSP / Lin-Kernighan-ге дейін қатты PLS-төмендету арқылы PLS-толық екендігі дәлелденді.^[16]
• Жергілікті-көппроцессорлық жоспарлау / k-өзгеріс салмақты-3Dөлшемді-сәйкестендіруден / (p, q) -Жергілікті-көппроцессорлық-жоспарлауға ауысу / (2p + q) -өзгеріске ауысу, мұндағы (2p + q) ) ≥ 8.^[5]
• Өзімшіл-көппроцессорлық-жоспарлау / k-өзгерту-қасиеті-t салмақты-3Dөлшемді-сәйкестендіру / (p, q) -Ауыстыру (2p + q) -Selfish-Multi-Processor-Scheduling / k-меншікті өзгерту -т, мұндағы (2p + q) ≥ 8.^[5]
• Табу таза Нэш тепе-теңдігі ішінде Жалпы-кептеліс-ойын / Өзгерту PLS-ді толық Positive-all-not-all-teng-max-3Sat / Flip-тен жалпы-кептеліске-ойынға / өзгеріске дейін қысқарту арқылы толық дәлелденген.^[17]
• Табу таза Нэш тепе-теңдігі ішінде Симметриялық жалпы-кептеліс-ойын / өзгеріс PLS-толық асимметриялық Жалпы-Кептелу-Ойын / Симметриялы Жалпы-Тығырық-Ойын / Өзгеріске ауыстыру арқылы қатты PLS-төмендету арқылы дәлелденді.^[17]
• Таза нәрсені табу таза Нэш тепе-теңдігі ан Асимметриялық Бағытталған-Желі-Кептелу-Ойындар / Өзгеріс Positive-all-teng-max-3Sat / Flip-тен бағытталған-желі-кептеліс-ойындарға / өзгеріске қатты қысқару арқылы PLS аяқталғандығы дәлелденді ^[17] сонымен қатар 2-табалдырықты ойындардан PLS-ті қысқарту арқылы / бағыт-желі-кептеліс-ойындарға / өзгертуге ауысу.^[18]
• Таза нәрсені табу таза Нэш тепе-теңдігі ан Асимметриялық бағытталмаған-Желі-кептеліс-ойындар / өзгеріс PLS-толық 2-табалдырық-ойындар / асимметриялы бағытталмаған-желілік-кептеліс-ойындар / өзгеріске ауысу арқылы қатты PLS-қысқарту арқылы дәлелденді.^[18]
• Таза нәрсені табу таза Нэш тепе-теңдігі ішінде 2-табалдырық-ойын / өзгеріс Max-Cut / Flip-тен 2-Threshold-Game / Change деңгейіне дейін қысқарту арқылы PLS-толық екендігі дәлелденді.^[18]
• А табу таза Нэш тепе-теңдігі жылы Нарықты бөлісу-ойын / өзгеріс полиномдық шектелген шығындар PLS-ті толықтай азайтып, 2-табалдырық-ойындардан / нарықты бөлісуге-ойынға / өзгеріске ауыстыру арқылы PLS-ті қысқарту арқылы дәлелденді.^[18]
• А табу таза Нэш тепе-теңдігі ан Қосымша-желілік-дизайн / өзгерту 2-табалдырықты-ойындардан / қабаттастырудан-желіден-дизайнға / өзгеріске ауыстыру арқылы PLS аяқталғандығы дәлелденді. Асимметриялы-бағытталған-желілік-тоқырау-ойын / өзгерісті дәлелдеуге ұқсас, қысқарту қатаң.^[18]
• Мин-0-1-бүтін бағдарламалау / k-Flip PLS-толық Min-4Sat-B ’/ Flip-тен Min-0-1-Integer Programming / k-Flip-ге дейін қысқарту арқылы PLS-толық екендігі дәлелденді.^[7]
• Max-0-1-бүтін бағдарламалау / k-Flip PLS-Max-0-1-Integer Programming / k-Flip деңгейіне дейін төмендетілгендіктен PLS-толық деп талап етіледі, бірақ дәлел жоқ.^[7]
• (p, q, r) -Макс-Шектеу-тағайындау
  • (3, 2, 3) -Макс-Шектеу-Тағайындау-3-партит / Өзгерту PLS-толық екендігі дәлелденді, ол PLS-ті қысқарту арқылы Circuit / Flip-тен (3, 2, 3) -Max-Contraint-Assignment-3-partite / Change-ке дейін қысқартады.^[19]
  • (2, 3, 6) -Макс-Шектеу-Тағайындау-2-партит / Өзгеріс PLS-толық екендігі дәлелденді, ол PLS-ті қысқарту арқылы Circuit / Flip-тен (2, 3, 6) -Max-Contraint-Assignment-2-partite / Change-қа дейін қысқартады.^[19]
  • (6, 2, 2) -Макс-Шектеу-тағайындау / өзгерту PLS-толық екені Circuit / Flip-тен (6,2, 2) -Max-Contraint-Assignment / Change мәніне дейін қысқарту арқылы дәлелденді.^[19]
  • (4, 3, 3) -Макс-Шектеу-тағайындау / өзгерту Max-4Sat- (B = 3) / Flip-ге тең және PLS-толық Max-circuit / Flip-тен PLS-төмендету арқылы толық екендігі дәлелденді.^[13] Төмендетуді кеңейтуге болады, сондықтан тығыздықты алуға болады.^[19]
• Жақын-түрлі-түсті политоп / өзгеріс Max-2Sat / Flip-тен жақын-түрлі-түсті политопқа / өзгеріске дейін PLS-төмендету арқылы PLS-толық екендігі дәлелденді.^[3]
• Stable-Configuration / Flip ішінде Хопфилд желісі PLS-толық екендігі дәлелденді, егер шекті мәндер 0 және салмақтар теріс болса, Max-Cut / Flip-тен Stable-Configuration / Flip-ге дейін қатты PLS-төмендету арқылы.^[1][8][16]
• Өлшемді-өлшемді-сәйкестендіру / (p, q) - Ауыстыру p ≥9 және q for 15 үшін PLS-толық (-2, 3, r) -Max-Constraint-Assignment-2-partite / Change-ден салмақталған-3Dөлшемді-сәйкестендіруге ауысу / p, q) - ауыстыру.^[5]

Әдебиеттер тізімі

• Яннакакис, Михалис (2009), «Тепе-теңдік, бекітілген нүктелер және күрделілік кластары», Информатикаға шолу, 3 (2): 71–85, CiteSeerX  10.1.1.371.5034, дои:10.1016 / j.cosrev.2009.03.004.