|
||||
Меню:
Главная
Форум
Литература: Программирование и ремонт Импульсные блоки питания Неисправности и замена Радиоэлектронная аппаратура Микросхема в ТА Рубрикатор ТА Кабельные линии Обмотки и изоляция Радиоаппаратура Гибкие диски часть 2 часть 3 часть 4 часть 5 Ремонт компьютера часть 2 Аналитика: Монтаж Справочник Электроника Мощные высокочастотные транзисторы 200 микросхем Полупроводники ч.1 Часть 2 Алгоритмические проблемы 500 микросхем 500 микросхем Сортировка и поиск Монады Передача сигнала Электроника Прием сигнала Телевидиние Проектирование Эвм Оптимизация Автомобильная электроника Поляковтрансиверы Форт Тензодатчик Силовые полевые транзисторы Распределение частот Резисторные и термопарные Оберон Открытые системы шифрования Удк |
[276] Докажите, что в классе Р все языки (кроме 0 и {0,1}*) полны относительно полиномиальной сводимости. 36.3-6 Покажите, что язык L полон в классе NP тогда и только тогда, когда язык L полон в со - NP. 36.3-7 Сводящий алгоритм F (лемма 36.6) строит схему С = /(ж), используя информацию об ж, А и к. Профессор заметил, что алгоритм F получает в качестве аргумента только ж, однако ни А, ни к ему не даны. (Поскольку язык L принадлежит NP, можно утверждать, что требуемые А и к существуют, но каковы они, мы не знаем.) На этом основании профессор делает вывод, что алгоритм F построить нельзя, и что язык CIRCUIT-SAT не обязан принадлежать NP. Объясните, в чём ошибка профессора. Доказательства NP-полноты. Доказывая NP-полноту языка CIRCUIT-SAT, мы проверяли, что всякий язык из класса NP сводится к CIRCUIT-SAT за полиномиальное время. Больше этого (рассматривать произвольный язык из класса NP) нам делать не придётся - чтобы доказать NP-полноту какого-либо языка, достаточно свести к нему другой язык, NP-полнота которого уже доказана. Таким способом мы докажем NP-полноту двух задач о выполнимости формул, а в разделе 36.5 - NP-полноту ещё нескольких задач. Другими словами, NP-полноту языков мы будем доказывать с помощью следующей леммы. Лемма 36.8 Если для языка L найдется язык V £ CNP, для которого V L, то язык L NP-труден. Если, кроме того, L £ NP, то С £ CNP. Доказательство Поскольку V £ CNP, любой язык L" из класса NP сводится к V. По условию V р L, поэтому по свойству транзитивности (упр. 36.3-1) L" L. Таким образом, язык L является NP-трудным. Если теперь L £ NP, то С £ CNP. Другими словами, нам не надо доказывать, что любой NP-язык сводится к интересующему нас - достаточно проверить это для одного NP-полного языка. Получаем такую схему доказательства NP-полноты языка L. 1.Доказываем, что L £ NP. 2.Выбираем какой-либо известный NP-полный язык V. 3.Строим алгоритм, вычисляющий функцию /, которая отображает входы задачи V во входы задачи L. 4.Доказываем, что функция / сводит V к L, то есть что ж £ С тогда и только тогда, когда /(ж) £ L. 5.Доказываем, что вычисляющий функцию / алгоритм работает полиномиальное время. Можно сказать и так: мы уже пробили брешь в стене, установив (36.2) NP-полноту одного языка, и теперь можем использовать это для доказательства NP-полноты других языков. Эти языки также можно использовать как эталонные при доказательстве NP-полноты, так что чем больше наша коллекция NP-полных языков, тем легче доказывать NP-полноту новых. Выполнимость формул Мы докажем NP-полноту задачи о выполнимости пропозициональных формул. (Именно для этой задачи впервые была доказана NP-полнота.) Вот как она формулируется. Пропозициональные формулы составлены из 1.булевых переменных х\, х2,... ; 2.булевских операций (пропозициональных связок) Л (конъюнкция, AND, И), V (дизъюнкция, OR, ИЛИ), -. (отрицание, НЕ, NOT), => (импликация, следование), <ФФ (эквивалентность, если и только если); 3.скобок. Так же как и для булевых схем, набором значений (truth assignment) для пропозицональной формулы Lp будем называть набор значений переменных, входящих в эту формулу. Выполняющим набором (satisfying assignment) мы называем набор значений, на котором формула принимает значение 1 (истинна). Формула называется выполнимой (satisfiable), если для неё существует выполняющий набор. Задача о выполнимости формулы (formula satisfiability problem) состоит в проверке, является ли заданная (пропозициональная) формула выполнимой. Другими словами, SAT = {(lp) : Lp - выполнимая булева формула}. Например, формула Lp = ({xi => х2) V -((-1ж1 <ФФ х3) V х4)) А -1ж2 имеет выполняющий набор (х\ = 0, х2 = 0, х3 = 1, х4 = 1), так как Lp = ((0 => 0) V -.((-.0 1) V 1)) Л -.0 = (1V-i(1V1))A1 = (1V0)A1 = 1, и, следовательно, данная формула Lp принадлежит SAT. Выполнимость формулы можно проверить, перебрав все наборы значений переменных. Однако этот переборный алгоритм не является полиномиальным (для формулы с п переменными есть 2п вариантов). Как показывает следующая теорема, задача SAT является NP-полной и потому для неё вряд ли существует полиномиальный алгоритм. Теорема 36.9 36.8 Сведение выполнимости схемы к выполнимости формулы. Для каждого провода схемы заводим переменную; формула представляет собой конъюнкцию утверждений о поведении каждого элемента. Задача о выполнимости формулы NP-полна. Доказательство Прежде всего убедимся, что SAT £ NP. В самом деле, сертификатом является выполняющий набор, а проверяющий алгоритм подставляет значения из этого набора на место переменных и вычисляет значение формулы. Осталось показать, что задача SAT NP-трудна. Для этого достаточно проверить, что CIRCUIT-SAT р SAT. Другими словами, мы должны по данной схеме построить формулу, которая будет выполнима в том и только том случае, когда исходная схема была выполнима. Можно построить формулу, которая вычисляет ту же функцию, что и заданная схема. Это делается просто: двигаясь от входов схемы к выходу, мы на каждом проводе пишем формулу, ему соответствующую (например, выходу элемента И соответствует формула <~р А ф, где <р и ф - формулы, соответствующие её входам). К сожалению, этот метод не является полиномиальным. Многократное использование одних и тех же подформул может привести к формуле экспоненциального размера (упр. 36.4-1). Поэтому нужно действовать более аккуратно. Трюк состоит в том, чтобы увеличить число переменных в формуле, введя дополнительную переменную для каждого провода в схеме, (а не только для её входов). Основная идея показана на рис. 36.8. Формула, которую строит сводящий алгоритм, есть конъюнкция переменной, соответствующей выходу схемы, и утверждений о корректности работы всех функциональных элементов. Например, схеме на рисунке 36.8 будет поставлена в соответствие формула ip = жюЛ(ж4 -1Ж3) Л(ж5 <5 -.(xi V ж2)) Л(ж6 -1Ж4) Л(Ж7 -Л ж2 Л ж3)) Л(ж8 -.(ж5 V ж6)) Л(ж9 <> ->(хе V Ж7)) Л(жю <5 ->(Ж7 Л Ж8 Л Жд)) Это построение, как легко видеть, приводит к схеме полиномиального размера и выполняется за полиномиальное время. Почему схема С выполнима тогда и только тогда, когда выполнима построенная формула р>1 Пусть схема С имеет выполняющий |
Среды: Smalltalk80 MicroCap Local bus Bios Pci 12С ML Микроконтроллеры: Atmel Intel Holtek AVR MSP430 Microchip Книги: Емкостный датчик 500 схем для радиолюбителей часть 2 (4) Структура компьютерных программ Автоматическая коммутация Кондиционирование и вентиляция Ошибки при монтаже Схемы звуковоспроизведения Дроссели для питания Блоки питания Детекторы перемещения Теория электропривода Адаптивное управление Измерение параметров Печатная плата pcad pcb Физика цвета Управлении софтверными проектами Математический аппарат Битовые строки Микроконтроллер nios Команды управления выполнением программы Перехода от ahdl к vhdl Холодный спай Усилители hi-fi Электронные часы Сердечники из распылённого железа Анализ алгоритмов 8-разрядные КМОП Классификация МПК История Устройства автоматики Системы и сети Частотность Справочник микросхем Вторичного электропитания Типы видеомониторов Радиобиблиотека Электронные системы Бесконтекстный язык Управление техническими системами Монтаж печатных плат Работа с коммуникациями Создание библиотечного компонента Нейрокомпьютерная техника Parser Пи-регулятор ч.1 ПИ-регулятор ч.2 Обработка списков Интегральные схемы Шина ISAВ Шина PCI Прикладная криптография Нетематическое: Взрывной автогидролиз Нечеткая логика Бытовые установки (укр) Автоматизация проектирования Сбор и защита Дискретная математика Kb радиостанция Энергетика Ретро: Прием в автомобиле Управление шаговым двигателем Магнитная запись Ремонт микроволновки Дискретные системы часть 2 | ||