как можно показать, какова связь между «гипотезой об уникальных играх» и «теоремой PCP»? Как объяснить, что «гипотеза об уникальных играх» является более сильной формой «теоремы...
Метод отрицательного противника ( ) - это SDP, характеризующий сложность квантового запроса. Это обобщение широко используемого метода противника ( A D V ), и оно преодолевает два барьера, мешающих противнику:A D V±ADВ±ADV^\pmA D VADВADV Барьер тестирования свойств: если все 0-экземпляры находятся...
Недавно я прочитал доказательство, которое намеревалось показать, что проблема была сильно NP-трудной, просто сводя ее (за полиномиальное время) от сильно NP-трудной задачи. Это не имело никакого смысла для меня. Я бы подумал, что вам нужно будет показать, что любые числа, использованные в...
задира Поскольку проблема длинная, здесь есть особый случай, который отражает ее суть. Проблема: Пусть A - детриминистический алгоритм для 3-SAT. Является ли проблема полного моделирования алгоритма A (на каждом экземпляре задачи). P-Space сложно? (Точнее, есть ли основания полагать, что эта задача...
Планарные графы имеют род ноль. Графы, встраиваемые в тор, имеют род не более 1. Мой вопрос прост: Есть ли какие-нибудь проблемы, которые полиномиально разрешимы на плоских графах, но NP-трудны на графах рода один? В более общем смысле, существуют ли проблемы, которые полиномиально разрешимы на...
Я учил нижних границ сегодня, и один из студентов спросил о причине названия C . Официальное объяснение состоит в том, что «А» означает «Чередование».AC0AC0AC^0A CAСAC Я смутно помню, как много лет назад мне сказали, что Ник Пиппенгер Стив Кук назвал честь Ника Пиппенджера (класс Ника), а позже Ник...
Укороченная версия. Первоначальное доказательство того, что # 2-SAT является #P -завершенным, фактически показывает, что экземпляры # 2-SAT являются монотонными (без учета отрицаний каких-либо переменных) и двудольными (график, образованный предложениями над Переменный является двудольным графом)...
Сложность схемы с ограниченной глубиной является одной из основных областей исследования в теории сложности схемы. Эта тема имеет происхождение в результатах типа «функция четности не в » и « функция mod не вычисляется », где - класс языков, разрешимых по неоднородности, постоянной глубине,...
Я ищу естественные примеры эффективных алгоритмов (т.е. в полиномиальном времени) их правильность и эффективность могут быть доказаны конструктивно (например, в PRAпрAPRA или ), ноHAЧАСAHA не известно никаких доказательств, использующих только эффективные концепции (то есть мы не знаем, как...
Недавно я столкнулся со следующим вариантом окраски краев. Для связного неориентированного графа найдите раскраску ребер, которая использует максимальное количество цветов, а также удовлетворяет ограничению, согласно которому для каждой вершины ребра, инцидентные используют не более двух...
Одна вещь, которую могут сделать квантовые компьютеры (возможно, даже с использованием только квантовых цепей с логарифмической глубиной BPP +), - это аппроксимировать выборку преобразования Фурье булевой -значной функции в P.± 1±1\pm 1 Здесь и ниже, когда я говорю о выборке преобразования Фурье, я...
Рассмотрим следующую задачу QQQ : Нам дано целое число и k интервалов [ l i , r i ] с 1 ≤ l i ≤ r i ≤ 2 n . Нам также даны 2 n целых чисел d 1 , … , d 2 n ≥ 0 . Задача состоит в том, чтобы выбрать минимальное количество интервалов [ l i , r i ]nnnkkk[li,ri][li,ri][l_i,r_i]1≤li≤ri≤2n1≤li≤ri≤2n1\leq...
При попытке убедить экономистов в актуальности теории сложности в печати, есть ли стандартная ссылка для цитирования? Я знаком с постом в блоге Ноама Нисана , опросом Тима Раугардена и 11-й статьей эссе Скотта Ааронсона . Эти посты доступны для компьютерных ученых, но не используют язык экономистов...
Я делаю обзор литературы по проблеме изоморфизма графов. Большинство статей, которые я читаю, написаны Э. М. Луксом и Ласло Бабаи. В этих работах используются знания высокого уровня теории групп и теории сложности. Поскольку я новичок в этой области, многие вещи мне не понятны. Может кто-нибудь...
Предположим, я рассматриваю следующий вариант BPP, который позволяет нам называть E (xact) BPP: язык находится в EBPP, если существует рандомизированный TG за полиномиальное время, который принимает каждое слово языка с вероятностью 3/4 и каждое слово не в язык с вероятностью 1/4. Очевидно, что...
При поиске Информационной системы о классах графов и их включениях я обнаружил несколько классов графов, для которых задача о гамильтоновом цикле NP-полна, а сложность задач о гамильтоновом пути НЕ известна. Некоторые из этих классов представляют собой двудольные графы максимальной степени 3,...
Следуя предложению Джоша Грохова, я превращаю свой комментарий из предыдущего вопроса в новый. Какие доказательства у нас есть для ?UP≠NPUP≠NP\mathsf{UP} \neq \mathsf{NP} Здесь - это класс языков, распознаваемых недетерминированными машинами Тьюринга за полиномиальное время, которые имеют...
Работа «Субквадратичные алгоритмы для 3SUM» Илья Баран, Эрик Д. Демейн, Михай Патраску имеет следующую сложность для Задача 3SUM: дать список LLL из NNn целых чисел, если х , у, z∈ LИкс,Y,Z∈Lx,y,z \in L такие, что х + у= z,Икс+Yзнак равноZ,x+y=z. w -вес-w-A C 0 O ( n 2 / w 2 log w ) O ( n 2 / ( M B...
Известно, что минимальный размер цепей, функцию четности, в точности равен . Нижняя оценка доказательства основана на методе исключения ворот.U2U2U_23 ( n - 1 )3(N-1)3(n-1) Недавно я заметил, что метод исключения затвора хорошо работает и для недетерминированных цепей, и мы можем доказать нижнюю...
При условии, что группа симметрии и две подгруппы и , имеет ли место ?SnSnS_nG,H≤SnG,H≤SnG, H\leq S_nπ∈Snπ∈Sn\pi\in S_nGπ∩H=∅Gπ∩H=∅G\pi\cap H=\emptyset Насколько я знаю, эта проблема известна как проблема пересечения смежных классов. Мне интересно, в чем сложность? В частности, известна ли эта...