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

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 .$m$$m=0.6 n$

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.$\Omega (2^{(0.4-\epsilon) n})$$\epsilon.$

Podemos ainda perguntar:

(i) Podemos ter um circuito desse tamanho ? 2 ( 1 - ϵ ) n ?$2^{0.9 n}$$2^{(1-\epsilon)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< n$$m=0.6n$$m$$m=n^\alpha$

$m$

$m$$m$

$m$$m^d$$d$

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.)

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