Есть ли оракул такой, что САТ не бесконечно часто в субэкспоненциальном времени?

Определим - как класс языков , для которого существует язык и для бесконечного множества , и согласны на всех экземплярах длины . (То есть это класс языков, которые могут быть «решены бесконечно часто, в субэкспоненциальном времени».) $io$ $SUBEXP$ $L$ $L' \in \cap_{\varepsilon > 0} TIME(2^{n^{\varepsilon}})$ $n$ $L$ $L'$ $n$

$A$ $NP^A \not\subset io$ $SUBEXP^A$ $A$ $SAT^A$

(Я задаю отдельные вопросы здесь, потому что мы должны быть осторожны с бесконечно часто-временными классами: просто потому, что у вас есть редукция от проблемы к проблеме а разрешима бесконечно часто, вы можете не получить, что разрешимо бесконечно часто без дополнительных предположений о сокращении: что, если ваше сокращение от «пропустит» входные длины, на которых вы можете решить ?) $B$ $C$ $C$ $B$ $B$ $C$

cc.complexity-theory sat oracles Райан Уильямс
источник

кажется расширением или вариацией идеи Бейкера Гилла Соловая 1975 года? это можно как-то противопоставить?

ВЗН

Ответы:

Вы можете просто взять оракула A st NP = EXP поскольку EXP не находится в io-subexp. Для SAT это зависит от кодировки, например, если единственные допустимые экземпляры SAT имеют четную длину, тогда легко определить SAT для строк нечетной длины. Но если вы используете такой язык, как тогда у вас все будет хорошо. $^A$ $^A$ $^A$ $L=\{\phi 01^*\ |\ \phi\in SAT^A\}$

Лэнс Фортноу
источник

Есть ли у вас какие - либо ссылки на концепцию Io классов сложности и разделения в литературе. В частности, я не совсем уверен , почему

. Кроме того, имеем ли мы (1)

E X P ⊈ i o

$EXP \nsubseteq io$

S U B E X P

$SUBEXP$

T I M E (f (n)) ⊈ i o

$TIME(f(n)) \nsubseteq io$

для соответствующих функций f (n), и (2)

означает

(или, по крайней мере,

T I M E (\frac{f (n)}{\log (f (n))})

$TIME(\frac{f(n)}{\log(f(n))})$

N P \subseteq i o

$NP \subseteq io$

P

$P$

P = N P

$P = NP$

N P \subseteq P / p o l y

$NP \subseteq P/ poly$

Майкл Вехар

Я думаю моя основная путаница , почему не может каждый

проблемы есть

алгоритма , который только решает проблему для множества длин входных

, где

является

ставит перед собой.

E X P

$EXP$

C o m p l e t e

$Complete$

i o

$io$

S U B E X P

$SUBEXP$

X

$X$

X

$X$

E X P

$EXP$

C o m p l e t e

$Complete$

Майкл Вехар

Другими словами, алгоритм

не помогает нам, потому что мы должны были бы решить

, чтобы знать, как использовать алгоритм

Но я не удивлюсь, если существующая работа от вас или других людей решит мой вопрос.

i o

$io$

S U B E X P

$SUBEXP$

X

$X$

i o

$io$

S U B E X P

$SUBEXP$

Майкл Вехар

@RyanWilliams Привет, Райан, есть мысли? Спасибо за ваше время. :)

Майкл Вехар

@RyanWilliams Спасибо за комментарий! Это помогло, и я думаю, что все получилось. Теперь кажется, что аргумент вообще не зависит от EXP, и его можно обобщить, чтобы доказать что-то вроде (1). Но ключевым моментом было «противоположное значение, по крайней мере, на одном входе этой длины ». Другими словами, аргумент в моей голове зависит от ИО определяется как согласование бесконечного числа входных длин (не просто просто бесконечно много входов). Я до сих пор не имею большой идеи о чем-то вроде (2). Еще раз спасибо и хорошего дня / ночи. :)

Майкл Вехар

Тебе не нужно идти на все, что Ланс предлагал. Например, относительно случайного оракула, использование оракула в качестве односторонней функции (скажем, вычисляемой в последовательных позициях битов) экспоненциально трудно инвертировать на всех, кроме конечного числа длин.

Эта проблема напрямую сводится к SAT на входе той же длины, поэтому из этого следует, что SAT ^ A не является бесконечно часто субэкспонированным.

Рассел Импальяццо
источник

Я должен сказать, что количество входов в схему одинаково, а не общий размер экземпляра. Однако, если вам разрешено заполнять размеры схем путем добавления избыточных предложений, вы сможете сделать любой код с фиксированным входным размером связанной односторонней функцией.

Рассел Импальяццо