В какой степени вычислительные способности для сложных задач помогают в решении простых задач

11

Короче говоря, вопрос заключается в следующем: в какой степени вычислительные способности для сложных задач действительно помогают вам в решении простых задач. (Могут быть разные способы сделать этот вопрос интересным и нетривиальным, и вот одна из таких попыток.)

Вопрос 1:

Рассмотрим схему решения SAT для формулы с n переменными. (Или для нахождения гамильтонова цикла для графа с ребрами.)n

Предположим, что каждый вентиль позволяет вычислить произвольную булеву функцию от переменных. Для конкретности возьмем m = 0,6 n .mm=0.6n

Гипотеза сильного экспоненциального времени (SETH) утверждает, что даже при таких сильных затворах нам нужен суперполиномиальный размер цепи. На самом деле нам нужен размер не менее для каждого ϵ . В некотором смысле, ворота на долю переменных, которые представляют очень сложные булевы функции (намного превосходящие NP-полноту), не дают вам большого преимущества.Ω(2(0.4ϵ)n)ϵ.

Мы можем также спросить:

(i) Можем ли мы иметь такую ​​схему размером ? 2 ( 1 - ϵ ) n ?20.9n2(1ϵ)n

Ответ «нет» будет значительным укреплением SETH. Конечно, может быть, есть простой ответ «да», который я просто скучаю.

(ii) Если ответом на (i) является ДА, то гейты, которые вычисляют произвольные булевы функции, дают некоторые преимущества по сравнению с вентилями, которые «просто» вычисляют (скажем) произвольные NP-функции; или просто меньшие экземпляры самого SAT?

Следующие попытки задать вопрос что - то похожее на вопросы в .P

Вопрос 2:

Как и прежде, пусть а для конкретности положим m = 0,6 n . (Другие значения m, такие как m = n α , также представляют интерес.) Рассмотрим следующие типы цепей:m<nm=0.6nmm=nα

а) За один шаг вы можете вычислить произвольную булеву функцию от переменных.m

б) За один шаг вы можете решить задачи SAT с переменными. Или, возможно, произвольная недетерминированная схема полиномиального размера от m переменных.mm

c) За один шаг вы можете выполнить произвольную схему для переменных размером m d ( d фиксировано).mmdd

г) За один шаг вы можете выполнить обычные логические элементы.

Рассмотрим вопрос о нахождении идеального соответствия для графа с ребрами. Соответствие имеет схему полиномиального размера. Вопрос в том, можно ли улучшить показатель степени в таком алгоритме согласования при переходе от цепей типа d) к цепям типа c), а также от цепей размера c) к цепям размера b) и из цепей размера b ) в цепи размера а).n

(Это может быть связано с известными проблемами параллельных вычислений или оракулов.)

Гил Калай
источник
1
На самом деле Strong ETH не так уж силен: он просто говорит, что вы не можете иметь единый алгоритм, работающий за времени для SAT с предложениями c n , для всех c . Разрешение произвольных булевых функций на небольшие наборы переменных помещает вас в область неоднородных цепей. «Неоднородный SETH» - интересный вариант, но я не думаю, что он изучен слишком близко. O(1.9999n)cnc
Райан Уильямс
Дорогой Райан, верно, мне просто удобнее рассматривать неоднородный случай. Отсутствие ответа на вопрос 1 будет значительным усилением неоднородной СЕТ. (Я думал, что неоднородный SETH как усиление SETH, но, возможно, я ошибался.) Возможно, вы можете переформулировать Вопросы 1 и 2 для унифицированных алгоритмов. В любом случае, возможно, с такими сильными версиями SETH и неоднородным SETH будет возможно найти контрпример.
Гил Калай
Я предполагаю, что вы хотите быть осторожным с тем, что : в SETH он обозначает количество переменных, в приведенном выше он, кажется, обозначает длину ввода. Если вы позволяете ворота , которые можно «вычислить SAT на .1 п переменных экземпляров» это тривиально , чтобы получить глубину 2 2 +0,9 п цепь размера для п переменной SAT: принимать или по всем возможным присвоений .9 п переменных, используйте свои ворота SAT, чтобы решить SAT на оставшихся .1 n переменных. Но это, вероятно, не то, что вы ищете .... Не так ли? n.1n2.9nn.9n.1n
Райан Уильямс

Ответы:

4

22msss=2nm

Боаз Барак
источник
1
Привет @ Боаз Барак. Вы не против, если я объединю ваши две учетные записи на этом сайте?
Лев Рейзин
1
Спасибо Вооз. Я предполагаю, что суть вопроса такова: если вы идете намного ниже того, что необходимо для вычисления всей функции, можете ли вы все еще вычислить полную функцию NP.
Гил Калай