Как всем известно, знаменитая книга Гэри и Джонсона (и многие другие) дает превосходный справочник по технике редукции в классической обстановке. Существуют ли какие-либо обзоры или книги на тему техники редукции в параметризованном алгоритме, скажем, редукция...
Я задал этот вопрос 10 дней назад на cs.stackexchange здесь, но у меня не было никакого ответа. В очень известной статье (в сетевом сообществе) Wang & Crowcroft представили некоторые результаты полноты вычисления пути при нескольких аддитивных / мультипликативных ограничениях. Первая проблема...
Есть ли способ закодировать экземпляр суммы подмножества или проблему разбиения числа так, чтобы (небольшое) решение целочисленного отношения дало ответ? Если не точно, то в каком-то вероятностном смысле? Я знаю, что LLL (и, возможно, PSLQ) использовались с умеренным успехом в решении задач Subset...
Как все знают, SAT завершен для сравнению с многозначным сокращением за полиномиальное время. Это все еще полные сокращения wrt много-один.NPNP\mathsf{NP}AC0AC0\mathsf{AC^0} Мои вопросы: какова минимальная необходимая глубина для сокращений? Более формально, Что наименьшее такое, что SAT - это...
Мне кажется, что большинство теоретиков сложности обычно верят в следующее философское правило: Если мы не можем найти эффективный алгоритм для задачи и можем свести проблему A к проблеме B , то, вероятно, эффективного алгоритма для проблемы B тоже нет.AAAAAABBBBBB Вот почему, например, когда новая...
Проблема: Учитывая представленный булевой схемой, генерируем равномерно случайный x ∈ { 0 , 1 } n такой, что ϕ ( x ) = 1 (или выводим ⊥, если таких нет х существует). ϕ : { 0 , 1 }N→ { 0 , 1 }φ:{0,1}N→{0,1}\phi : \{0,1\}^n \to \{0,1\}x ∈ { 0 , 1 }NИкс∈{0,1}Nx \in \{0,1\}^nϕ ( x ) = 1φ(Икс)знак...
Класс сложности PPAD был изобретен Христосом Пападимитриу в его основополагающей статье 1994 года . Этот класс предназначен для охвата сложности задач поиска, когда существование решения гарантируется «аргументом четности в ориентированных графах»: если в ориентированном графе существует...
Лэнс Фортноу недавно заявил, что доказательство L! = NP должно быть проще, чем доказательство P! = NP : Отдельный NP от логарифмического пространства. Я дал четыре подхода в обзоре диагонализации перед разделом 2001 года (Раздел 3), хотя ни один из них не удался. Должно быть намного проще, чем...
На прошлой неделе я снова читал текст Лесли Лампорта, опубликованный в 1982 году, на конференции, которую он дал о « Решенных проблемах, нерешенных проблемах и проблемах в параллелизме» . Бумага легко читается, но одна из вещей, которая заставила меня задуматься, это следующее утверждение: Можно ли...
Некоторое время назад я опубликовал справочный запрос для задач с графами, где мы хотим найти 2-секционное ребро, в котором оба набора удовлетворяют свойству, не связанному с их количеством элементов. Я пытался доказать, что следующая проблема NP-трудна: Для турнира существует ли множество дуг...
Могут ли все последующие одновременно выполняться? LsLsL_s содержится в для всех натуральных чисел . sLs+1Ls+1L_{s+1}sss L=⋃sLsL=⋃sLsL = \bigcup_s L_s - это язык всех конечных слов над .{0,1}{0,1}\{0,1\} Существует некоторый класс сложности и понятие соответствующего сокращения для такой , что для...
Когда мы хотим доказать , что является -полных, то стандартный подход выставляться полиномиальное время вычислимой сокращение многих один из известного -полных задачи в . В этом контексте нам не нужно жестко ограничивать время выполнения сокращения. Достаточно иметь любую полиномиальную границу,...
«Если , существует ли x , y ∈ N , a x 2 + b y = c » является N P -полным.a,b,c∈Na,b,c∈Na,b,c\in\Bbb Nx,y∈Nx,y∈Nx,y\in\Bbb Nax2+by=cax2+by=cax^2+by=cNPNP\mathsf{NP} К какому классу сложности относится «При условии , существуют ли x , y ∈ N , a x 2 + b y 2 = c »?a,b,c∈Na,b,c∈Na,b,c\in\Bbb...
Эта статья доказывает, что в игре с дверями и прижимными плитами PSPACE сложно определить, может ли аватар (игрока) достичь определенного места. Это подтверждается сокращением от TQBF , а длина полученных решений экспоненциально зависит от количества универсальных квантификаторов в формуле. Есть ли...
Уникальная SAT является хорошо известной проблемой: учитывая формулу CNF , верно ли, что F имеет ровно одну модель?FFFFFF Меня интересует проблема «точно -SAT»: учитывая формулу CNF F и целое число m > 1 , правда ли, что F имеет ровно m моделей?мmmFFFm > 1m>1m>1FFFmmm Обе проблемы выглядят...
Интересно, равны ли классы NPC, определенные сокращениями «многие-один» и сокращениями Тьюринга? Редактировать: Другой вопрос, являются ли сокращения Тьюринга только свертыванием классов C и co-C для некоторого C или существует класс такой как существует проблема не в при сокращении Карпа, а в в...
Поскольку 2 NP-полные задачи по определению сводимы друг к другу, поэтому решение одной из них можно получить с помощью черного ящика, решающего другую, почему они не имеют сходных отношений аппроксимации (ссылаясь на их аналоги по оптимизации )? Я предполагаю, что некоторый постоянный или даже...
В параметризованной сложности люди используют сокращение с фиксированным параметром (FPT), чтобы доказать W [t] -твердость. Теоретически FPT-редукция не является редукцией за полиномиальное время, поскольку она может экспоненциально выполняться по параметру k. Но на практике все сокращения FPT,...
Этот вопрос не может быть техническим. Как не носитель языка и ТА для класса алгоритма, я всегда задавался вопросом, что означает гаджет в «гаджете-предложении» или «гаджете-переменной». В словаре говорится, что гаджет - это машина или устройство, но я не уверен, какое это имеет разговорное...
Существует ли со следующими свойствами:L ∈ N PL∈NPL\in {\bf NP} Известно , что влечет P = N P .L ∈ PL∈PL\in {\bf P}P = N PP=NP{\bf P}={\bf NP} Там нет (известного) полинома Тьюринга уменьшения (или какой -либо другой Н Р -полной проблемы) к L .SА ТSATSATН ПNP{\bf NP}LLL Другими словами, если...