Зведення з застосуванням «регуляторів»: завдання здійсненності

Привіт, Хаброжители! Ми вирішили опублікувати уривок з книги «Алгоритми: розробка і застосування. Класика Computers Science». Завдання SAT і 3-SAT. Припустимо, є безліч X n булевих змінних x1, ..., xn; кожна змінна може приймати значення 0 або 1 (еквіваленти false і true). Литералом по X називається одна із змінних xi або її заперечення. Нарешті, умовою називається звичайна диз'юнкція літералів image

А тепер дамо формальне визначення присвоювання значень, які відповідають набору умов. Логічним присвоюванням для X називається присвоювання значення 0 або 1 кожному xi; іншими словами, це функція ν: X → {0,1}. Присвоювання v неявно задає значення істинності, протилежне xi. Присвоювання виконує умову C, якщо після нього C дає результат 1 за умовами булевої логіки; це еквівалентно вимогу про те, щоб принаймні один з символів C мав значення 1. Присвоювання виконує сукупність умов C1, ..., Ck, якщо в результаті його все Ci дають результат 1; інакше кажучи, якщо в результаті його кон'юнкція
image
Логічне присвоювання ν, яке задає всім трьом змінним значення 1, не є виконують, тому що з них не виконується друга з перелічених умов; з іншого боку, присвоювання ν', яке задає всім змінним значення 0, є виконуючим.

Тепер можна навести формулювання задачі здійснимості, також позначається SAT:
Для заданого безлічі умов C1, ..., Ck по безлічі змінних X = {x1, ..., xn} існує виконує логічне присвоювання?

Існує приватний випадок SAT, володіє еквівалентною складністю, але при цьому більш зрозумілий; в ньому всі умови містять рівно три буквальне (що відповідають різним змінним). Назвемо цю задачу завданням 3-здійснимості, або 3-SAT:

Для заданого безлічі умов C1, ..., Ck, кожне з яких має довжину 3, по безлічі змінних X = {x1, ..., xn}, існує виконує логічне присвоювання?

Завдання здійсненності і 3-здійсненності є фундаментальними завданнями комбінаторного пошуку; вони містять основні складові складної обчислювальної задачі і в гранично спрощеному вигляді. Потрібно прийняти n незалежних рішень (привласнення всім xi) так, щоб виконати набір обмежень. Існують різні способи виконання кожного обмеження окремо, але рішення доведеться комбінувати так, щоб всі обмеження виконувалися одночасно.

Зведення задачі 3-SAT до задачі про незалежній множині
А тепер зв'яжемо обчислювальну складність, втілену в задачах SAT і 3-SAT, з іншого (на перший погляд) складністю, представленої пошуком незалежних множин і верхових покриттів у графах, а саме: ми покажемо, що 3-SAT ≤P Незалежне безліч. Основна трудність в подібних доказах очевидна: в задачі 3-SAT мова йде про присвоювання значень булевими змінними з урахуванням обмежень, тоді як завдання про незалежній множині спрямована на вибір вершин у графі. Щоб вирішити примірник завдання 3-SAT з використанням «чорного ящика» для задачі про незалежній множині, необхідно якось закодувати всі ці булеві обмеження у вузлах і ребрах графа, щоб критерій здійсненності відповідав існування великого незалежного безлічі.

Цей прийом демонструє загальний принцип проектування складних відомостей Y ≤P X: побудова «регуляторів» з компонентів у задачі X для представлення того, що відбувається в задачі Y.

(8.8) 3-SAT ≤P Незалежне безліч.

Доказ. Є «чорний ящик» для задачі про незалежній множині; ми хочемо вирішити примірник завдання 3-SAT, що складається з змінних X = {x1, ..., xn} і умов C1, ..., Ck.

Щоб правильно поглянути на проблему відомості, слід зрозуміти, що існують дві концептуально різні точки зору на примірник 3-SAT.

— Перший спосіб подання примірника 3-SAT був запропонований раніше: для кожної з n змінних приймається незалежне рішення 0/1, а успіх досягається при досягненні одного з трьох способів виконання кожної умови.

— Той же примірник 3-SAT можна уявити інакше: потрібно вибрати один текст з кожної умови, а потім знайти логічне присвоювання, в результаті якого усі ці рядки дають результат 1 з виконанням всіх умов. Отже, успіх досягається в тому випадку, якщо ви зможете вибрати текст з кожної умови так, щоб ніякі два обраних літерала не «конфліктували»; ми говоримо, що конфлікт двох літералів виникає тоді, коли один дорівнює змінної xi, а інший її заперечення. Якщо вдасться уникнути конфліктів, ми зможемо знайти логічне присвоювання, в результаті якого вибрані літерали з кожної умови дають результат 1.

Наступне зведення базується на другому поданні примірника 3-SAT; ми можна закодувати його з використанням незалежних множин у графі. Спочатку побудуємо граф G = (V, E), що складається з 3k вузлів, згрупованих у k трикутників, як показано на рис. 8.3. Таким чином, для i = 1, 2, ..., k будуються три вершини vi1, vi2, vi3, сполучені один з одним ребрами. Кожній вершині присвоюється мітка; vij позначається j-м литералом з умови Ci примірника 3-SAT.

image

Перш ніж продовжувати, розглянемо, як виглядають незалежні безлічі з розміром k на цьому графі: так як дві вершини не можуть бути обрані з одного трикутника, вони складаються з усіх способів вибору однієї вершини з кожного трикутника. Так реалізується наша мета за вибором літерала в кожному умові, який дає результат 1; але поки ми не зробили нічого, щоб запобігти конфлікт між двома текстовими значеннями.

Конфлікти будуть кодуватися додаванням нових ребер в граф: кожну пару вершин, мітки яких відповідають конфліктуючим литералам, ми з'єднуємо ребром. Чи призведе це до знищення всіх незалежних множин розміру k або таке безліч існує? Це залежить від того, можна вибрати один вузол з кожного трикутника, щоб при цьому не були обрані конфліктуючі пари вузлів. Але ж саме те, що потрібно в примірнику 3-SAT!

Стверджується, що вихідний примірник завдання 3-SAT виконаємо в тому і тільки в тому випадку, якщо побудований граф G має незалежне безліч з розміром не менше k. По-перше, якщо примірник 3-SAT виконаємо, то кожен трикутник у графі містить як мінімум один вузол, мітка якого дає результат 1. Нехай S — множина, що складається з одного такого сайту в кожному трикутнику. Множина S є незалежним; якби між двома вузлами u, v повинні були б конфліктувати; але це неможливо, так як обидві вони дають результат 1.

І навпаки, припустимо, що граф G містить незалежна множина S з розміром не менше k. Тоді насамперед розмір S дорівнює точно k, і воно повинно з — тримати один вузол з кожного трикутника. Далі стверджується, що існує логічне присвоювання ν для змінних у примірнику 3-SAT, що володіє тим властивістю, що мітки всіх вузлів S дають результат 1. Як же побудувати таке присвоювання ν? Для кожної змінної xi, якщо xi, ні не використовується як мітка вузла в S, ми присвоюємо ν(xi) = 1. В іншому разі або xi, або є міткою вузла в S; тому що якщо б один вузол S був позначений xi, а інший, то ці два вузли були б з'єднані ребром, що суперечило б нашим припущенням про те, що S є незалежною множиною. Якщо xi є міткою вузла в S, ми присвоюємо ν(xi) = 1; в іншому випадку виконується присвоювання ν(xi) = 0. При такій побудові ν всі мітки вузлів в S дають результат 1.

Так як G містить незалежне безліч з розміром не менше k в тому і тільки в тому випадку, якщо оригінальний примірник 3-SAT було виготовити зведення завершено.

Посилання на огляд самої книги тут
Джерело: Хабрахабр

0 коментарів

Тільки зареєстровані та авторизовані користувачі можуть залишати коментарі.