Гаджет (информатика) - Gadget (computer science)
В теории сложности вычислений , гаджет представляет собой подмножество экземпляра задачи, моделирующее поведение одного из основных единиц различной вычислительной задачи. Гаджеты обычно используются для построения сокращений от одной вычислительной задачи к другой, как часть доказательств NP-полноты или других типов вычислительной сложности. Компонент конструкции метод представляет собой способ построения сокращений с помощью гаджетов.
Сабо (2009) прослеживает использование гаджетов в 1954 году в статью теории графов по WT Татта , в котором Tutte при условии устройства для снижения проблемы нахождения подграфа с заданными степенями ограничения к идеальным согласующим проблемам. Однако терминология «гаджет» имеет более позднее происхождение и не встречается в статье Тутте.
Пример
Многие доказательства NP-полноты основаны на редукции «многие единицы» из 3-выполнимости , проблеме поиска удовлетворительного присваивания булевой формуле, которая представляет собой конъюнкцию (логическое и) предложений, причем каждое предложение является дизъюнкцией (логическим или) трех термины, и каждый термин является логической переменной или ее отрицанием. Сведение этой проблемы к сложной задаче на неориентированных графах , такой как проблема гамильтонова цикла или раскраска графа , обычно будет основано на гаджетах в форме подграфов, которые имитируют поведение переменных и предложений данного экземпляра 3-выполнимости. . Затем эти устройства будут склеены вместе, чтобы сформировать единый граф, сложный пример рассматриваемой проблемы графа.
Например, проблема проверки 3-раскрашиваемости графов может быть доказана NP-полной путем редукции от 3-выполнимости этого типа. Для сокращения используются две специальные вершины графа, помеченные как «Земля» и «Ложь», которые не являются частью какого-либо гаджета. Как показано на рисунке, гаджет для переменной x состоит из двух вершин, соединенных в треугольник с вершиной земли; одна из двух вершин гаджета помечена x, а другая - отрицанием x . Устройство для предложения ( t 0 ∨ t 1 ∨ t 2 ) состоит из шести вершин, соединенных друг с другом, с вершинами, представляющими термы t 0 , t 1 и t 2 , а также с основной и ложной вершинами посредством показаны края. Любую формулу 3-CNF можно преобразовать в график, построив отдельный гаджет для каждой из его переменных и предложений и соединив их, как показано.
В любой 3-раскраске результирующего графа можно обозначить три цвета как истинный, ложный или основной, где ложь и земля - это цвета, присвоенные ложной и основной вершинам (обязательно разные, поскольку эти вершины становятся смежными с помощью конструкция), а true - оставшийся цвет, не используемый ни одной из этих вершин. В гаджете переменной возможны только две раскраски: вершина, помеченная переменной, должна быть окрашена в истинное или ложное значение, а вершина, помеченная отрицанием переменной, должна быть соответственно окрашена в ложь или истину. Таким образом, действительные присвоения цветов гаджетам переменных соответствуют один к одному с присвоениями истинности переменным: поведение гаджета в отношении окраски имитирует поведение переменной в отношении назначения истинности. Каждое присваивание предложения имеет допустимую 3-раскраску, если хотя бы одна из его соседних вершин терма окрашена в истинный цвет, и не может быть 3-раскрашенной, если все его соседние вершины термов окрашены в ложь. Таким образом, гаджет предложения может быть раскрашен тогда и только тогда, когда соответствующее присвоение истинности удовлетворяет предложению, поэтому снова поведение гаджета имитирует поведение предложения.
Ограниченные скидки
Agrawal et al. (1997) рассмотрели то, что они назвали «радикально простой формой сокращения устройства», в которой каждый бит, описывающий часть устройства, может зависеть только от ограниченного числа битов ввода, и использовали эти сокращения, чтобы доказать аналог Бермана. –Гипотеза Хартманиса о том, что все NP-полные множества изоморфны по полиномиальному времени.
Стандартное определение NP-полноты включает в себя полиномиальную редукцию многих единиц : проблема в NP по определению является NP-полной, если каждая другая проблема в NP имеет редукцию этого типа к ней, и стандартный способ доказательства того, что проблема в NP является NP-полной - это найти полиномиальное сокращение много-единицы от известной NP-полной задачи к ней. Но (в том, что Агравал и др. Назвали «любопытным, часто наблюдаемым фактом»), все множества, которые в то время были NP-полными, можно было доказать, используя более сильное понятие AC 0 редукций многие-один: то есть редукций, которые могут быть вычислены схемами полиномиального размера, постоянной глубины и неограниченного разветвления. Agrawal et al. Доказано, что каждый набор, который является NP-полным при AC 0 редукциях, является полным при еще более ограниченном типе редукции NC 0 много-однозначных редукций, использующих схемы полиномиального размера, постоянной глубины и ограниченного разветвления. В редукции NC 0 каждый выходной бит редукции может зависеть только от постоянного числа входных битов,
Гипотеза Бермана – Хартманиса - нерешенная проблема в теории сложности вычислений, утверждающая, что все NP-полные классы задач изоморфны по полиномиальному времени. То есть, если A и B - два NP-полных класса проблем, существует однозначное сокращение от A до B за полиномиальное время, обратное преобразование которого также вычислимо за полиномиальное время. Agrawal et al. использовал их эквивалентность между AC 0 сокращениями и NC 0 сокращениями , чтобы показать , что все наборы полных для NP под AC 0 сокращений являются AC 0 -изоморфен.
Оптимизация гаджетов
Одно из применений гаджетов - это доказательство точности результатов аппроксимации путем уменьшения проблемы, которую, как известно, трудно аппроксимировать, к другой проблеме, твердость которой необходимо доказать. В этом приложении обычно имеется семейство экземпляров первой проблемы, в которых есть пробел в значениях целевой функции, и в которых трудно определить, имеет ли данный экземпляр целевая функция, которая находится на низкой стороне или на высокой стороне разрыва. Редукции, используемые в этих доказательствах, и устройства, используемые в редукциях, должны сохранять существование этого разрыва, и сила результата о неприближаемости, полученного в результате редукции, будет зависеть от того, насколько хорошо этот разрыв сохраняется.
Trevisan et al. (2000) формализовали проблему поиска гаджетов, сохраняющих пробелы, для семейств задач удовлетворения ограничений, в которых цель состоит в том, чтобы максимизировать количество удовлетворяемых ограничений. В качестве примера они приводят сокращение от 3-выполнимости до 2-выполнимости по Garey, Johnson & Stockmeyer (1976) , в котором гаджет, представляющий предложение 3-SAT, состоит из десяти предложений 2-SAT, и в котором присвоение истинности, которое удовлетворяет предложению 3-SAT также удовлетворяет по крайней мере семи пунктам в гаджете, в то время как присвоение истинности, которое не удовлетворяет пункту 3-SAT, также не удовлетворяет более шести пунктам гаджета. Используя этот гаджет и тот факт, что (если P = NP ) не существует схемы полиномиального приближения для максимизации количества предложений 3-SAT, которым удовлетворяет назначение истинности, можно показать, что аналогичным образом не существует схемы аппроксимации для MAX. 2-СБ.
Trevisan et al. показывают, что во многих случаях изучаемых ими проблем удовлетворения ограничений устройства, приводящие к максимально сильным результатам несовместимости, могут быть построены автоматически в качестве решения задачи линейного программирования . Те же сокращения на основе гаджетов можно использовать и в другом направлении, чтобы переносить алгоритмы аппроксимации от более простых задач к более сложным задачам. Например, Trevisan et al. предоставить оптимальное устройство для сокращения 3-SAT до взвешенного варианта 2-SAT (состоящего из семи взвешенных предложений 2-SAT), более сильного, чем вариант, предложенный Garey, Johnson & Stockmeyer (1976) ; используя его вместе с известными алгоритмами аппроксимации полуопределенного программирования для MAX 2-SAT, они обеспечивают алгоритм аппроксимации для MAX 3-SAT с коэффициентом аппроксимации 0,801, что лучше, чем известные ранее алгоритмы.