Random 3-SAT: Qual é o intervalo experimental de consenso do limiar?

A proporção crítica de cláusulas para variáveis para o 3-SAT aleatório é maior que 3 e menor que 6 e parece ser comumente descrita como "em torno de 4,2" ou "em torno de 4,25". Mezard, Parisi e Zecchina provam (no sentido da física) que a razão crítica é de 4.256, enquanto o primeiro e o terceiro autores provam que é 4.267.

What is the range of values that the critical ratio could possibly take?

A motivação para mim fazer esta pergunta é que, se a proporção puder ser , então a redução padrão de 3-SAT para NAE-3-SAT (transformandocláusulasevariáveis emcláusulasevariáveis) fornece uma razão de, o que parece improvável, mas seria bastante legal. $2+\sqrt{5} \approx 4.236$ $m$ $n$ $2m$ $m+n+1$ $\phi$

sat phase-transition random-k-sat Andrew D. King
fonte

Você precisa definir o que significa uma proporção ser crítica.

Tyson Williams

Penso que esta é a terminologia padrão: o rácio crítico é o número real

tais que aleatórias fórmulas 3-SAT com

cláusulas são quase certamente satisfiable, e aleatória fórmulas 3-SAT com

cláusulas são quase certamente não satisfatório. quase certamente aqui significa que a probabilidade vai para

como

α

$\alpha$

< α n

$< \alpha n$

> α n

$> \alpha n$

1

$1$

n \to \infty

$n \to \infty$

Sasho Nikolov 5/13/13

possível duplicata de Quais são os limites superiores e inferiores mais conhecidos atualmente no limiar de (in) satisfação para k-sat aleatório e / ou 3-sat?

András Salamon

Eu afirmo que a questão é distinta. Estou procurando uma estimativa do conjunto de valores que, por exemplo, não chocariam nenhum especialista da comunidade. Eu não acho que nada abaixo de 4, por exemplo, se qualifique. (Sei que esta é, em certa medida, sujeitas a quilometragem individual.)

Andrew D. rei

Random 3-SAT: Qual é o intervalo experimental de consenso do limiar?

Respostas: