Até que ponto, a capacidade computacional para tarefas difíceis ajuda a resolver tarefas fáceis

11

Em resumo, a questão é: até que ponto, a capacidade computacional para tarefas difíceis realmente ajuda você a resolver tarefas fáceis. (Pode haver várias maneiras de tornar essa pergunta interessante e não trivial, e aqui está uma dessas tentativas.)

Questão 1:

Considere um circuito para resolver SAT para uma fórmula com n variáveis. (Ou para encontrar o ciclo hamiltoniano para um gráfico com arestas.)n

Suponha que todo portão permita o cálculo de uma função booleana arbitrária em variáveis. Para concretude, vamos tomar m = 0,6 n .mm=0.6n

A hipótese do tempo exponencial forte (SETH) afirma que, mesmo com portões tão fortes, precisamos do tamanho do circuito superpolinomial. De fato, precisamos do tamanho de pelo menos para cada ϵ . Em certo sentido, portas na fração das variáveis ​​que representam funções booleanas muito complicadas (muito além da completude do NP) não oferecem muita vantagem.Ω(2(0.4ϵ)n)ϵ.

Podemos ainda perguntar:

(i) Podemos ter um circuito desse tamanho ? 2 ( 1 - ϵ ) n ?20.9n2(1ϵ)n

Uma resposta “não” será um vasto fortalecimento do SETH. Claro, talvez exista uma resposta fácil "Sim", que eu simplesmente sinto falta.

(ii) Se a resposta a (i) for SIM, os portões que calculam funções booleanas arbitrárias oferecem algumas vantagens em comparação aos portões que “apenas” calculam (digamos) funções NP arbitrárias; ou apenas instâncias menores do próprio SAT?

P

Questão 2:

m<nm=0.6nmm=nα

m

mm

mmdd

d) Em uma etapa, você pode executar portões booleanos comuns.

n

(Isso pode estar relacionado a problemas conhecidos sobre computação paralela ou sobre oráculos.)

Gil Kalai
fonte
1
O(1.9999n)cnc
Caro Rayan, certo, me sinto mais confortável em considerar o caso não uniforme. Uma resposta sem resposta à pergunta 1 será um vasto fortalecimento do SETH não uniforme. (Eu pensei que o SETH não uniforme como um fortalecimento do SETH, mas talvez eu estivesse errado.) É possível reformular as perguntas 1 e 2 para algoritmos uniformes. Em qualquer caso, talvez com versões tão fortes de SETH e SETH não uniformes, seja possível encontrar um contra-exemplo.
Gil Kalai
n.1n2.9nn.9n.1n

Respostas:

4

22msss=2nm

Boaz Barak
fonte
1
Olá, @Boaz Barak. Você se importaria se eu mesclasse suas duas contas neste site?
Lev Reyzin
1
Obrigado Boaz. Acho que o espírito da pergunta é o seguinte: se você ficar bem abaixo do necessário para calcular todas as funções, ainda poderá calcular uma função completa de NP.
Gil Kalai