|
||||
Меню:
Главная
Форум
Литература: Программирование и ремонт Импульсные блоки питания Неисправности и замена Радиоэлектронная аппаратура Микросхема в ТА Рубрикатор ТА Кабельные линии Обмотки и изоляция Радиоаппаратура Гибкие диски часть 2 часть 3 часть 4 часть 5 Ремонт компьютера часть 2 Аналитика: Монтаж Справочник Электроника Мощные высокочастотные транзисторы 200 микросхем Полупроводники ч.1 Часть 2 Алгоритмические проблемы 500 микросхем 500 микросхем Сортировка и поиск Монады Передача сигнала Электроника Прием сигнала Телевидиние Проектирование Эвм Оптимизация Автомобильная электроника Поляковтрансиверы Форт Тензодатчик Силовые полевые транзисторы Распределение частот Резисторные и термопарные Оберон Открытые системы шифрования Удк |
[274] щим алгоритмом (reduction algorithm). Рисунок 36.3 иллюстрирует определение сводимости языка L\ к языку L2 за полиномиальное время. Каждый язык есть подмножество множества {0,1}*. Сводящая функция переводит любое слово х £ L\ в слова f(x) £ L2, а слово х L\ - в слово f(x) L2. Поэтому, если мы узнаем, принадлежит ли слово f(x) языку L2, мы тем самым получим ответ на вопрос о принадлежности слова х языку L\. Лемма 36.3 Если язык L\ С {0,1}* сводится за полиномиальное время к языку L2 С {0,1}*, то то из L2 £ Р следует L\ £ Р. Доказательство Пусть А2 - полиномиальный алгоритм, распознающий язык L2, a F - полиномиальный алгоритм, сводящий язык L\ к языку L2. Построим алгоритм А\, который будет за полиномиальное время разрешать язык L\. Рисунок 36.4 иллюстрирует построение. Получив вход х £ {0,1}*, алгоритм А\ (с помощью алгоритма F) получает f(x) и с помощью алгоритма А2 проверяет, принадлежит ли слово f(x) языку L2. Результат работы алгоритма А2 на слове f(x) и выдается алгоритмом А\ в качестве ответа. Определение (36.1) гарантирует, что алгоритм А\ даёт правильный ответ; он полиномиален, поскольку полиномиальны алгоритмы F и Аг (упр. 36.1-6). NP-полнота Понятие сводимости позволяет придать точный смысл утверждению о том, что один язык не менее труден, чем другой (с точностью до полинома). Запись L\ L2 можно интерпретировать так: сложность языка L\ не более чем полиномиально превосходит сложность языка L2. Наиболее трудны в этом смысле NP-полные задачи. Язык L С {0,1}* называется NP-полным (NP-complete), если 1.L £ NP. 2.V Р L для любого V £ NP Класс NP-полных языков будем обозначать NPC. Языки, которые обладают свойством 2 (но не обязательно обладают свойством 1), называют NP-трудными (NP-hard) Основное свойство NP-полных языков состоит в следующем: Теорема 36.4 Если некоторая NP-полная задача разрешима за полиномиальное время, то Р = NP. Если в классе NP существует задача, не разрешимая за полиномиальное время, то все NP-полные задачи таковы. Доказательство Пусть L - NP-полный язык, который одновременно оказался разрешимым за полиномиальное время (L £ Р и L £ NPC). Тогда для любого V £ NP по свойству 2 определения NP-полного язы- 36.5 Предполагаемое соотношение между классами P. NP и NPC. Классы Р и NPC содержатся в NP (что очевидно), и, можно полагать, не пересекаются и не покрывают всего NP. ВНИМАНИЕ: внутри треугольников с кружочками надо написать НЕ, внутри гнутых треугольников - ИЛИ, внутри кривых прямоугольников - И. Два набора входных данных для задачи CIRCUIT-SAT. (а) Набор входных значений (х\ = 1,х2 = 1,жз = 0) даёт значение 1 на выходе, так что эта схема выполнима. (Ь) Для этой схемы никакой набор входных значений не приводит к единице на выходе, так что эта схема не выполнима. ка имеем V L. Следовательно, V £ Р (лемма 36.3), и первое утверждение теоремы доказано. Второе утверждение теоремы является переформулировкой первого. Таким образом, гипотеза Р ф NP означает, что NP-полные задачи не могут быть решены за полиномиальное время. Большинство экспертов полагает, что это действительно так; предполагаемое соотношение между классами Р, NP и CNP показано на рис. 36.5. Конечно, мы не можем быть уверены, что однажды кто-нибудь не предъявит полиномиальный алгоритм для решения NP-полной задачи и не докажет тем самым, что Р = NP. Но пока что этого никому не удалось, и потому доказательство NP-полноты некоторой задачи является убедительным аргументом в пользу того, что она является практически неразрешимой. Задача о выполнимости для схем Как мы уже говорили, мы начнём с одной конкретной задачи; установив её NP-полноту, можно доказывать NP-полноту других задач методом сведения. В качестве такой задачи мы рассмотрим задачу о выполнимости для схем (circuit-satisfyability problem, или CIRCUIT-SAT). К сожалению, подробное доказательство NP-полноты этой задачи требует рассмотрения технических деталей, выходящего за рамки данной книги. Поэтому мы ограничимся неформальным наброском доказательства, полагая, что читатель имеет представление о схемах из функциональных элементов (см. гл. 29). На рисунке 36.6 показаны две схемы из функциональных элементов. Обе имеют по три входа и по одному выходу. Будем рассматривать наборы значений булевых переменных, соответствующих входам схем (truth assignments). Схема из функциональных элементов с одним выходом называется выполнимой (satisfiable), если существует выполняющий набор (satisfying assignment), то есть такой набор значений входов, при котором на выхо- де схемы появляется единица. Например, схема рис. 36.6(a) имеет выполняющий набор (х\ = 1, х2 = 1, жз = 0) и потому является выполнимой. В то же время никакие значения переменных ж1,ж2,жз для схемы рис. 36.6(6) не приводят к появлению 1 на выходе. Следовательно, эта схема невыполнима. Задача о выполнимости схемы (circuit-satisfiability problem) требует выяснить, «является ли данная схема, составленная из элементов И. ИЛИ и НЕ, выполнимой». Конечно, нужно договориться о способе представления булевых схем с помощью строк битов - это делается естественным образом (подобно тому, как это делается для графов); при этом размер полученной строки битов не более чем полиномиально зависит от размера схемы. Зафиксировав такое представление, рассмотрим язык CIRCUIT-SAT = {(С) : С - выполнимая схема из функциональных элементов} Задачу о выполнимости можно сформулировать так: можно ли данную схему заменить на эквивалентную, в которой выход соединён напрямую с нулевым проводом. Разумеется, можно узнать, выполнима ли данная схема, перебрав все возможные комбинации значений входов. К сожалению, их много: для схемы с к входами придется перебрать 2к наборов - время работы такого переборного алгоритма не ограничено полиномом (от к, или, что то же, от размера схемы). Как мы уже отмечали, большинство специалистов уверены, что что задача о выполнимости схемы не может быть решена полиномиальным алгоритмом (поскольку NP-полна). Для начала убедимся, что задача CIRCUIT-SAT принадлежит классу NP. Лемма 36.5 Задача CIRCUIT-SAT принадлежит классу NP. Доказательство Сертификатом является набор входных значений, при которых выходное значение равно 1 - ясно, что этот факт легко проверить за полиномиальное время. Для доказательства NP-полноты задачи CIRCUIT-SAT нам осталось доказать, что данная задача NP-трудна, то есть что любая задача из класса NP сводится к задаче CIRCUIT-SAT за полиномиальное время. Полное доказательство этого утверждения довольно громоздко, так что мы дадим лишь набросок доказательства. Коротко напомним, как устроен компьютер. Программа хранится в памяти компьютера в виде последовательности инструкций (команд). Инструкции содержат код операции, которую нужно выполнить, адреса аргументов (операндов) команды и адрес, по которому следует записать результат операции. В специальном месте памяти, которое называется счётчиком команд (program counter), хранится адрес текущей команды. Этот адрес в процессе выполнения программы меняется (постепенно увеличиваясь при выполне- |
Среды: 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 | ||