Гаджет (информатика)
В теории сложности вычислений гаджет — это часть экземпляра задачи, которая имитирует поведение одной из фундаментальных единиц другой вычислительной задачи. Гаджеты обычно используются для создания редукций одной вычислительной задачи к другой в рамках доказательства NP-полноты или других типов вычислительной сложности. Техника проектирования компонентов — это метод построения сокращений с помощью гаджетов. [1]
Сабо (2009) прослеживает использование гаджетов до статьи теории графов по У.Т. Тутте 1954 года , в которой Тутте представил гаджеты для сведения проблемы поиска подграфа с заданными степени ограничениями к задаче идеального сопоставления . Однако терминология «гаджетов» имеет более позднее происхождение и не встречается в статье Тутте. [2] [3]
Пример
[ редактировать ]
Многие доказательства NP-полноты основаны на редукциях «многих единиц» из 3-выполнимости , проблемы поиска удовлетворяющего присвоения булевой формуле, которая представляет собой соединение (логическое и) предложений, причем каждое предложение является дизъюнкцией (логическое или) трех термины, причем каждый термин представляет собой логическую переменную или ее отрицание. Сведение этой проблемы к сложной проблеме на неориентированных графах , такой как проблема гамильтонова цикла или раскраска графа , обычно будет основано на гаджетах в виде подграфов, которые моделируют поведение переменных и предложений данного экземпляра 3-выполнимости. . Затем эти гаджеты будут склеены вместе, чтобы сформировать единый граф, что является сложным примером рассматриваемой проблемы с графами. [4]
Например, задача проверки 3-раскрасимости графов может быть доказана NP-полной путем редукции от 3-выполнимости этого типа. При сокращении используются две специальные вершины графа, помеченные как «Земля» и «Ложь», которые не являются частью какого-либо гаджета. Как показано на рисунке, гаджет для переменной x состоит из двух вершин, соединенных треугольником с базовой вершиной; одна из двух вершин гаджета помечена знаком x , а другая помечена отрицанием x . Гаджет для предложения ( t 0 ∨ t 1 ∨ t 2 ) состоит из шести вершин, соединенных друг с другом, с вершинами, представляющими термины t 0 , t 1 и t 2 , а также с основными и ложными вершинами с помощью показаны края. Любую формулу 3-CNF можно преобразовать в график, создав отдельный гаджет для каждой из ее переменных и предложений и соединив их, как показано. [5]
В любой трехцветной раскраске результирующего графа можно обозначить три цвета как истинные, ложные или основные, где ложь и земля — это цвета, присвоенные ложной и основной вершинам (обязательно разные, поскольку эти вершины делаются смежными посредством конструкция), а true — оставшийся цвет, не используемый ни одной из этих вершин. Внутри переменного гаджета возможны только две раскраски: вершина, помеченная переменной, должна быть окрашена либо в истинный, либо в ложный цвет, а вершина, помеченная отрицанием переменной, должна быть соответственно окрашена в либо ложный, либо истинный цвет. Таким образом, действительные присвоения цветов переменным гаджетам соответствуют истинностным присвоениям переменным один к одному: поведение гаджета в отношении раскраски имитирует поведение переменной относительно истинностного присвоения.Каждое назначение предложения имеет действительную 3-цветную окраску, если хотя бы одна из соседних вершин терма окрашена в истинный цвет, и не может быть 3-цветной, если все смежные вершины термина окрашены в ложный цвет. Таким образом, гаджет предложения можно раскрасить тогда и только тогда, когда соответствующее истинностное присвоение удовлетворяет этому предложению, поэтому поведение гаджета снова моделирует поведение предложения.
Ограниченные скидки
[ редактировать ]Агравал и др. (1997) рассмотрели то, что они назвали «радикально простой формой редукции гаджета», в которой каждый бит, описывающий часть гаджета, может зависеть только от ограниченного числа бит входных данных, и использовали эти редукции для доказательства аналога Бермана –Гипотеза Хартманиса, утверждающая, что все NP-полные множества изоморфны полиномиально по времени. [6]
Стандартное определение NP-полноты включает в себя за полиномиальное время редукции «много-один» : проблема в NP по определению является NP-полной, если каждая другая проблема в NP имеет к ней редукцию этого типа, и стандартный способ доказательства того, что проблема в NP NP является NP-полной - найти полиномиальное время много-единой редукции известной NP-полной задачи к ней. Но (что Агравал и др. назвали «любопытным, часто наблюдаемым фактом») все множества, известные в то время как NP-полные, можно было доказать полными, используя более сильное понятие AC. 0 сокращения «многие-единицы»: то есть сокращения, которые можно вычислить с помощью схем полиномиального размера, постоянной глубины и неограниченного веера. Агравал и др. доказал, что любое множество, NP-полное относительно AC 0 сокращение завершается при еще более ограниченном типе сокращения, NC 0 сокращения «многие единицы» с использованием схем полиномиального размера, постоянной глубины и ограниченного разветвления. В НК 0 При уменьшении каждый выходной бит сокращения может зависеть только от постоянного числа входных бит. [6]
Гипотеза Бермана-Хартманиса - это нерешенная проблема теории сложности вычислений, утверждающая, что все NP-полные классы задач изоморфны по полиномиальному времени. То есть, если A и B — два NP-полных класса задач, существует взаимно однозначное сокращение от A до B за полиномиальное время , обратное решение которого также вычислимо за полиномиальное время. Агравал и др. использовали их эквивалентность между AC 0 редукции и NC 0 сокращения, чтобы показать, что все наборы полны для NP при AC 0 сокращения переменного тока 0 -изоморфный. [6]
Оптимизация гаджетов
[ редактировать ]Одним из применений гаджетов является доказательство сложности результатов аппроксимации путем сведения задачи, которую, как известно, трудно аппроксимировать, к другой задаче, сложность которой необходимо доказать. В этом приложении обычно имеется семейство примеров первой задачи, в которых существует разрыв в значениях целевой функции и в которых трудно определить, имеет ли данный пример целевую функцию, которая находится на нижней стороне или на высокой стороне разрыва. Редукции, используемые в этих доказательствах, и устройства, используемые при редукции, должны сохранять существование этого пробела, и сила результата о неаппроксимируемости, полученного в результате редукции, будет зависеть от того, насколько хорошо сохраняется этот пробел.
Тревизан и др. (2000) формализовали проблему поиска устройств, сохраняющих пробелы, для семейств задач удовлетворения ограничений , целью которых является максимизация количества удовлетворяемых ограничений. [7] В качестве примера они приводят сокращение от 3-выполнимости к 2-выполнимости, предложенное Гари, Джонсоном и Стокмейером (1976) , в котором устройство, представляющее предложение 3-SAT, состоит из десяти предложений 2-SAT, и в котором истинностное задание, удовлетворяет пункту 3-SAT, также удовлетворяет как минимум семи пунктам гаджета, в то время как присвоение истинности, которое не удовлетворяет пункту 3-SAT, также не удовлетворяет более чем шести пунктам гаджета. [8] Используя этот гаджет и тот факт, что (если только P = NP ) не существует схемы аппроксимации с полиномиальным временем для максимизации числа предложений 3-SAT, которым удовлетворяет присвоение истинности, можно показать, что аналогично не существует схемы аппроксимации для MAX. 2-СБ.
Тревизан и др. показывают, что во многих случаях изучаемых ими задач удовлетворения ограничений устройства, приводящие к максимально возможным результатам неаппроксимируемости, могут быть созданы автоматически как решение задачи линейного программирования . Те же самые сокращения на основе гаджетов можно использовать и в другом направлении, чтобы перенести алгоритмы аппроксимации от более простых задач к более сложным. Например, Тревизан и др. предоставить оптимальное приспособление для сокращения 3-SAT до взвешенного варианта 2-SAT (состоящего из семи взвешенных пунктов 2-SAT), который более силен, чем вариант Гари, Джонсона и Стокмейера (1976) ; используя его вместе с известными алгоритмами аппроксимации полуопределенного программирования для MAX 2-SAT, они обеспечивают алгоритм аппроксимации для MAX 3-SAT с коэффициентом аппроксимации 0,801, лучшим, чем ранее известные алгоритмы.
Ссылки
[ редактировать ]- ^ Гэри, MR ; Джонсон, Д.С. (1979), «3.2.3 Проектирование компонентов», Компьютеры и трудноразрешимые проблемы: Руководство по теории NP-полноты , Сан-Франциско, Калифорния: WH Freeman, стр. 72–74 , ISBN 0-7167-1045-5 , МР 0519066 .
- ^ Сабо, Хасинт (2009), «Хорошие характеристики для подграфов с некоторой степенью ограничений», Журнал комбинаторной теории , серия B, 99 (2): 436–446, doi : 10.1016/j.jctb.2008.08.009 , MR 2482961 .
- ^ Тутте, WT (1954), «Краткое доказательство факторной теоремы для конечных графов», Canadian Journal of Mathematics , 6 : 347–352, doi : 10.4153/CJM-1954-033-3 , hdl : 10338.dmlcz/101241 , МР 0063008 .
- ^ Сипсер, Майкл (1997), «Введение в теорию вычислений» , PWS Publishing Co., стр. 260 .
- ^ Это сокращение описано в Гольдрайх, Одед (2008), Вычислительная сложность: концептуальная перспектива , издательство Кембриджского университета, предложение 2.27, стр. 81, ISBN 978-1-139-47274-6 .
- ^ Перейти обратно: а б с Агравал, Маниндра ; Аллендер, Эрик ; Импальяццо, Рассел ; Питасси, Тонианн ; Рудич, Стивен (1997), «Снижение сложности сокращений», Труды 29-го симпозиума ACM по теории вычислений (STOC '97) , стр. 730–738, doi : 10.1145/258533.258671 , ISBN 0-89791-888-6 . Агравал, Маниндра ; Аллендер, Эрик ; Рудич, Стивен (1998), «Снижение сложности схемы: теорема об изоморфизме и теорема о разрыве», Journal of Computer and System Sciences , 57 (2): 127–143, doi : 10.1006/jcss.1998.1583 .
- ^ Тревизан, Лука ; Соркин, Грегори Б.; Судан, Мадху ; Уильямсон, Дэвид П. (2000), «Гаджеты, аппроксимация и линейное программирование», SIAM Journal on Computing , 29 (6): 2074–2097, doi : 10.1137/S0097539797328847 , MR 1756405 .
- ^ Гэри, Майкл Р .; Джонсон, Дэвид С .; Стокмейер, Ларри (1976), «Некоторые упрощенные NP-полные задачи на графах», Theoretical Computer Science , 1 (3): 237–267, doi : 10.1016/0304-3975(76)90059-1 .