-полная задача с квазиполиномиальной оценкой числа решений

15

FewP - это класс -задач с полиномиальной оценкой числа решений (во входном размере). Там нет никакого известного Св.нут P -полные проблемы в ф х ш Р . Мне интересно, как далеко мы можем расширить это наблюдение.NPNPfewP

Существует ли естественная -полная проблема с квазиполиномиальной верхней оценкой числа решений (свидетелей)? Есть ли общепринятая гипотеза, которая исключает такую ​​возможность?NP

Естественный означает, что проблема не является искусственно созданной проблемой, чтобы ответить на вопрос (или аналогичные), и люди интересуются проблемой независимо (как определено Каве).

РЕДАКТИРОВАТЬ: Щедрость будет присуждаться за такую ​​естественную -полную проблему или разумный аргумент, исключающий существование таких проблем (используя широко принятые гипотезы теории сложности).NP

Мотивация: Моя интуиция заключается в том, что -полнота накладывает суперполиномиальную (или даже экспоненциальную) нижнюю границу числа свидетелей.NP

Мухаммед Аль-Туркистани
источник
1
Проблема обещание UniqueSAT в (не то же самое , как U P ), который является подмножеством Р г о м I сек е F е ш Р (не то же самое , как F е ш Р ) , PromiseUPUPPromiseFewPFewP
Джошуа Грохов
3
Будет ли дополнение SAT ответить на ваш вопрос?
Каве
1
В этом весь смысл - это не так; размер ввода - это количество битов на входе, и (разреженные) экземпляры 3-sat имеют размер . Количество переменных является лишь одним аспектом (параметром) входных данных, поэтому для других задач (скажем, проблем с графами) нужно было бы указать, как измеряется количество свидетелей в терминах. Например, для максимального среза входной граф может иметь n 2 ребер, и опять же есть только 2 n свидетелей (что является субэкспоненциальным по входному размеру ). Но мы действительно хотим измерить с точки зрения п . Однако не очевидно, что #vertices - правильная мера. mlognn22nn
Даниелло
2
@Kaveh Да, так что вы должны предположить, что Мухаммед думал о том, что имеет смысл в его вопросе. Также, как видите, сложность зоопарка согласуется с моим определением. В общем, в любом интересном классе сложности определение не должно меняться, если вы добавляете ввод полиномом.
domotorp
5
@ downvoters Почему, черт возьми, люди опровергают этот вопрос? Я имею в виду, по крайней мере, кто-то может дать причину для этого ...
Domotorp

Ответы:

11

Это очень интересный вопрос.

Сначала уточняющее замечание. Обратите внимание, что «верхняя граница числа свидетелей» не является свойством вычислительной проблемы как таковой, но конкретного верификатора, используемого для решения задачи , так же как «верхняя граница числа состояний» не будет свойство проблемы, но решающая ее машина Тьюринга. Таким образом, высказывание « проблема N P с верхней границей числа решений» не совсем точно, и если P = N P, то у каждой задачи N P есть верификатор с любым количеством желаемых решений (включая ноль и включая все возможные строки) ,NPNPP=NPNP

Поэтому мы должны дать определение, чтобы ответить на ваш вопрос. Для , скажем, задача N P L «имеет не более s ( n ) решений», если для некоторой константы c существует O ( n c ) -временной верификатор V такой, что для каждой входной длины n и для каждый x L длины n , есть различные y 1 , , y s ( ns:NNNPLs(n)cO(nc)VnxLn длины n c такой, чтоV(x, y i )принимает для всехi, аV(x,y)отклоняет все остальныеyдлины n c .y1,,ys(n)ncV(x,yi)iV(x,y)ync

Все, что я могу сказать на данный момент, так это:

  1. Каждый -полная проблема , которую я знаю (определяются некоторыми естественными проверяющим) имеет очевидную соответствующую # P версию -полным подсчета (с тем же проверяющим).NP#P
  2. Для любого -полным задачи , определенной с верификатор , имеющие не более р ø л у ( п ) решений (или даже 2 п о ( 1 ) решений) соответствующий счет версия , вероятно, не # Р -полная.NPpoly(n)2no(1)#P

Более подробно: предположим, что является N P -полным, с верификатором V, который имеет не более O ( n c ) решений. Тогда естественный подсчет "решение" версия L , который мы определяем какLNPVO(nc)L

CountL(x):=the number of y such that V(x,y) accepts

вычислим в , то есть, функция полиномиальных по с O ( журнал п ) запросов к N P . Это потому , что решить , является ли число решений й не больше к находится в N P : свидетель, если он существует, это просто число у я «s делает V принять, что мы знаем , что в большинстве O ( п в )FPNP[O(logn)]O(logn)NPxkNPyiVO(nc), Тогда мы можем бинарный поиск , используя эту задачу вычислить точное число решений L .NPL

Следовательно, -полная проблема такого рода не может быть распространена на # P -полную проблему обычным способом, если только # P F P N P [ O ( log n ) ] . Это выглядит маловероятным; вся полиномиальная иерархия времени в основном рухнет до P N P [ O ( log n ) ] .NP#P#PFPNP[O(logn)]PNP[O(logn)]

Если вы предполагаете в вышеприведенном, вы все равно получите маловероятные последствия. Вы бы показали, что # P можно вычислить за 2 n o ( 1 ) времени с помощью оракула N P. Например, этого более чем достаточно, чтобы доказать, что E X P N PP P, а затем E X P N PP / p o l ys(n)=2no(1)#P2no(1)NPEXPNPPPEXPNPP/poly, Не то, чтобы эти разделения были маловероятными, но кажется маловероятным, что они были бы доказаны с помощью алгоритма оракула времени субэкспозиции для Перманента.NP

Кстати, я не сказал ничего слишком проницательного здесь. В литературе почти наверняка есть такой аргумент.

Райан Уильямс
источник
Действительно, это проницательный ответ.
Мохаммед Аль-Туркистани