Existe um oráculo tal que SAT não é infinitamente frequente no tempo subexponencial?

Defina - para ser a classe de idiomas modo que exista um idioma e para infinitos , e concordar em todos os casos de comprimento . (Ou seja, esta é a classe de idiomas que pode ser "resolvida infinitamente com frequência, em tempo subexponencial".) $io$ $SUBEXP$ $L$ $L' \in \cap_{\varepsilon > 0} TIME(2^{n^{\varepsilon}})$ $n$ $L$ $L'$ $n$

Existe um oráculo tal que - ? Se equiparmos SAT com o oráculo da maneira usual, podemos dizer que não está nesta classe? $A$ $NP^A \not\subset io$ $SUBEXP^A$ $A$ $SAT^A$

(Estou fazendo perguntas separadas aqui, porque precisamos ter cuidado com as classes de tempo infinitamente freqüentes: apenas porque você tem uma redução do problema $B$ para o problema $C$ e $C$ é solucionável infinitamente, você pode não entender que $B$ é solucionável infinitamente, sem outras suposições sobre a redução: e se a sua redução de $B$ "perder" os comprimentos de entrada nos quais você pode resolver $C$ ?)

cc.complexity-theory sat oracles Ryan Williams
fonte

parece uma extensão ou variação da idéia de Baker Gill Solovay 1975? pode ser contrastado de alguma forma?

vzn

Respostas:

Você pode simplesmente pegar o oráculo A st NP $^A$ = EXP $^A$ já que EXP não está no io-subexp. Para SAT $^A$ isso depende da codificação, por exemplo, se as únicas instâncias SAT válidas tiverem um comprimento par, será fácil resolver o SAT em cadeias de comprimento ímpar. Mas se você usar um idioma como $L=\{\phi 01^*\ |\ \phi\in SAT^A\}$ , deverá ficar bem.

Lance Fortnow
fonte

Você tem referências ao conceito de io classes de complexidade e separações na literatura. Em particular, não sei ao certo por que - . Além disso, temos (1) - para funções apropriadas f (n) e (2) - implica (ou pelo menos )?

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$

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$

Michael Wehar

Eu acho que minha principal confusão é por que todo problema - não pode ter um algoritmo - que só resolve o problema para um conjunto de comprimentos de entrada onde é o próprio conjunto - .

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$

Michael Wehar

Em outras palavras, o algoritmo - não nos ajuda, porque teríamos que decidir para saber como usar o algoritmo - . Mas não ficaria surpreso se o trabalho existente de você ou de outras pessoas resolver minha pergunta.

i o

$io$

S U B E X P

$SUBEXP$

X

$X$

i o

$io$

S U B E X P

$SUBEXP$

Michael Wehar

@RyanWilliams Oi Ryan, algum pensamento? Obrigado pelo seu tempo. :)

Michael Wehar

@RyanWilliams Obrigado pelo comentário! Ajudou e acho que resolvi. Agora, parece que o argumento não depende de EXP e isso pode ser generalizado para provar algo como (1). Mas, o ponto principal era "o valor oposto em pelo menos uma entrada desse comprimento ". Em outras palavras, o argumento em minha cabeça depende io sendo definido como concordar com um número infinito de comprimentos de entrada (não simplesmente apenas infinitamente muitas entradas). Ainda não tenho muita ideia de algo como (2). Mais uma vez obrigado e tenha um bom dia / noite. :)

Michael Wehar

Você não precisa se esforçar para sugerir que Lance estava sugerindo. Por exemplo, em relação a um oráculo aleatório, usar o oráculo como uma função unidirecional (por exemplo, avaliada em posições de bits consecutivas) é exponencialmente difícil de inverter em todos os comprimentos, exceto finitos.

Esse problema é reduzido diretamente para SAT na mesma entrada de comprimento; portanto, segue que SAT ^ A não está infinitamente subexp.

Russell Impagliazzo
fonte

Devo dizer que o número de entradas no circuito é o mesmo, não o tamanho total da instância. No entanto, se você puder aumentar o tamanho dos circuitos adicionando cláusulas redundantes, poderá transformar qualquer código de tamanho de entrada fixo em uma função unidirecional relacionada.

Russell Impagliazzo