Quais são os melhores limites inferiores atuais no 3SAT?

46

Quais são os melhores limites inferiores de corrente para o tempo e a profundidade do circuito para o 3SAT?

cc.complexity-theory lower-bounds sat Joe Fitzsimons
fonte

43

Até onde eu sei, o limite inferior de tempo conhecido como "independente do modelo" para o SAT é o seguinte. Seja e o tempo de execução e o espaço vinculado a qualquer algoritmo SAT. Então devemos ter infinitamente frequentemente. Nota . (O resultado que Suresh cita é um pouco obsoleto.) Esse resultado apareceu no STACS 2010, mas é um resumo extenso de um artigo muito mais longo, que você pode obter aqui: $T$ $S$ $T \cdot S \geq n^{2 \cos(\pi/7) - o(1)}$ $2 \cos(\pi/7) \approx 1.801$ http://www.cs.cmu.edu/~ryanw/automated-lbs.pdf

Obviamente, o trabalho acima se baseia em muitos trabalhos anteriores mencionados no blog de Lipton (consulte a resposta de Suresh). Além disso, à medida que o limite do espaço S se aproxima de n, o limite inferior do tempo T também se aproxima de n. Você pode provar uma "troca de espaço-tempo" melhor nesse regime; veja a pesquisa de Dieter van Melkebeek sobre os limites inferiores do espaço de tempo SAT a partir de 2008.

Se você se restringir a máquinas de Turing multitape, poderá provar infinitamente com frequência. Isso foi provado por Rahul Santhanam e segue de um limite inferior semelhante, conhecido pelos PALINDROMES neste modelo. Acreditamos que você deve ser capaz de provar um limite inferior quadrático que é "independente de modelo", mas que é ilusório há algum tempo. $T \cdot S \geq n^{2-o(1)}$

Para circuitos não uniformes com fan-in delimitado, não conheço um limite inferior de profundidade melhor que . $\log n$

Ryan Williams
fonte

2

estamos trabalhando nisso. Veja este link: meta.cstheory.stackexchange.com/questions/3/latex-math-support

Suresh Venkat

2

T \cdot S \leq n^{2 \cos (π / 7) + o (1)}

$T \cdot S \leq n^{2 \cos(\pi/7)+o(1)}$

2

T \cdot S

$T \cdot S$

T \cdot S = Ω (n^{2 - o (1)})

$T \cdot S = \Omega(n^{2-o(1)})$

2

@ Warren, não exatamente, tanto quanto eu sei. Limites inferiores como o Yao são para o modelo de programa de ramificação baseado em comparação , que não é tão expressivo quanto uma máquina de acesso aleatório de uso geral. Pode-se imaginar resolver a distinção de elementos sem nenhuma comparação direta entre os elementos.

Ryan Williams

1

@Turbo, o melhor limite inferior para o 3sat com muitas cláusulas linearmente é o mesmo que escrevi, porque a redução de sat para 3sat é extremamente local. A leitura da literatura sobre o tópico também mostrará isso.

Ryan Williams

17

$o(n)$ $n^c$ $c$ $\sqrt{3}$

Suresh Venkat
fonte

1

n^{o (1)}

$n^{o(1)}$

o (n)

$o(n)$

11

$\Omega(n^c)$ $c > 1$

Lev Reyzin
fonte

4

Meu entendimento é o mesmo que Lev Reyzin. É possível que exista um algoritmo determinístico completo para SAT que seja executado no espaço O (n) e no tempo O (n). É incrível que a existência de um algoritmo tão eficiente não seja proibida.

Giorgio Camerani
fonte

Quais são os melhores limites inferiores atuais no 3SAT?

Respostas: