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

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

Вопрос 1:

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

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

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

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

(i) Можем ли мы иметь такую ​​схему размером ? 2 ( 1 - ϵ ) n ?$2^{0.9 n}$$2^{(1-\epsilon)n}$

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

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

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

Вопрос 2:

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

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

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

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

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

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

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

$2^{2^m \cdot s}$$s$$s=2^{n-m}$