Quão comum é a transição de fase em problemas NP-completos?

É sabido que muitos problemas NP-completos exibem transição de fase. Estou interessado aqui na transição de fase com relação à contenção na linguagem, em vez da dureza da entrada, relativa a um algoritmo.

Para tornar o conceito inequívoco, vamos defini-lo formalmente da seguinte forma. Uma língua $L$ exibe transição de fase (com relação à contenção), se

1. Existe um parâmetro de ordem $r(x)$ , que é uma função com valor real computável em tempo polinomial da instância.

2. Existe um limite $t$ . É uma constante real ou pode depender de $n=|x|$, ou seja, $t=t(n)$ .

3. Para quase todos os com r ( x ) < t , temos x ∈ L . ( Quase todos os meios aqui: todos, exceto muitos, ou seja, a proporção se aproxima de 1, como n → $x$$r(x)<t$$x\in L$$n\rightarrow\infty$ ).

4. Para quase todo com r ( x ) > t , temos x ∉ $x$$r(x)>t$$x\notin L$ .

5. Para quase todo , ele mantém esse r ( x ) ≠ t . (Ou seja, a região de transição é "estreita".)$x$$r(x)\neq t$

Muitos problemas naturais completos de NP exibem transição de fase nesse sentido. Os exemplos são inúmeras variantes do SAT, todas as propriedades de gráficos monotônicos, vários problemas de satisfação de restrições e provavelmente muitos outros.

Pergunta: Quais são algumas exceções "legais"? Existe um problema natural de NP completo, que (provavelmente) não possui uma transição de fase no sentido acima?

Pesquisadores especialistas nesta área basicamente afirmam que as transições de fase são uma característica universal dos problemas completos de NP, embora isso ainda precise ser formulado / provado rigorosamente e ainda não seja amplamente considerado / disseminado em um campo maior (emana mais de uma abordagem empírica). ramo de estudo). é quase uma conjectura aberta. há fortes evidências. não há candidatos plausíveis para problemas completos de PN sem transição de fase. Aqui estão dois árbitros que apóiam esse pov:

• Transições de fase em problemas NP-completos: um desafio para probabilidade, combinatória e ciência da computação / Moore

• Comportamento de transição de fase / Walsh (ppt)

aqui está um esboço da verdade da afirmação. tem a ver com P contido no NP completo. um problema / linguagem completo do NP deve ter instâncias solucionáveis ​​no tempo P e outras solucionáveis ​​no tempo exponencial (ou pelo menos superpolinomial) se P ≠ NP. mas sempre deve haver uma maneira de "agrupar" as instâncias P das instâncias "não-P". portanto, sempre deve haver sempre alguns "critérios de transição" entre as instâncias P e não-P. em suma, talvez esse fenômeno esteja associado de maneira intrísica ao P ≠ NP!

outro argumento aproximado: todos os problemas completos de NP são intercambiáveis ​​por meio de reduções. se uma transição de fase for encontrada em uma única, ela deve ser encontrada em todas elas.

evidência mais circunstancial para isso, mais recentemente (~ 2010) foi mostrada a transição de fase para limites mais baixos em circuitos monótonos para detecção de cliques em gráficos aleatórios.

• Complexidade média de casos de detecção de panelinhas / Rossman

divulgação completa: Moshe Vardi estudou transições de fase particularmente no SAT e tem uma visão mais cética contrastante nesta palestra / vídeo.

• Transições de fase e complexidade computacional

$G_{n,m}$$n$$m$$\binom{n}{2}$$m$$G_{n,m}$

A coloração C dos gráficos regulares D tem uma série de transições discretas, não particularmente faseadas, a menos que você estique.

Aqui está uma tabela de resultados de coloração, que vou enviar para o SAT17. Observe que 3 cores de 6 gráficos regulares são impossíveis, exceto em alguns exemplos. Da mesma forma, 4 cores dos gráficos do décimo grau ... Os gráficos C3D5N180 são levemente difíceis. O C4D9 Golden Point está apenas provisoriamente em C4D9N180; Os gráficos C4D9 são os 4cnfs mais difíceis por tamanho que encontrei; portanto, o C4D9 se qualifica como um "ponto difícil". O ponto C5D16 de ouro é conjecturado para existir, mas estaria na região do ponto duro de 5 para 6 cores.

          Universal Constants of Regular Graph Coloring

As fórmulas de coloração têm variáveis ​​lgC por vértice, para um total de variáveis ​​lgC * N; as arestas têm cláusulas de coloração C, para um total de cláusulas C * M. Existem algumas cláusulas adicionais por vértice para excluir cores extras. Os Golden Points são os N menores, de modo que: A colorabilidade de C em gráficos de grau D com N vértices é quase sempre satisfatória, com probabilidade próxima a 1. Para Alta Probabilidade, N instâncias aleatórias eram satisfatórias. Para Very High, N * N foram satisfatórios. Para Super High, as instâncias aleatórias N * N * N foram satisfatórias.

Os pontos de coloração dourados da Alta Probabilidade (1 - 1 / N) são:

C3D5N180 C4D6N18 C4D7N35 C4D8N60 C4D9N180? C5D10N25 C5D11N42 C5D12N72

Os pontos de coloração dourados de Probabilidade Muito Alta (1 - 1 / (N * N)) são:

C3D5N230? C4D6N18 C4D7N36 C4D8N68 C4D9N ??? C5D10N32 C5D11N50 C5D12N78

Os pontos de coloração dourada com super alta probabilidade (1 - 1 / (N * N * N)) são:

C3D5N ??? C4D6N22 C4D7N58 C4D8N72? C4D9N ??? C5D10N38 C5D11N58 C5D12N ??

Todas as instâncias aleatórias no estudo foram satisfatórias. Os pontos de probabilidade linear conferiram centenas de fórmulas satisfatórias. Os pontos de probabilidade quadrática verificaram dezenas de milhares de fórmulas satisfatórias. Os pontos cúbicos de probabilidade verificaram centenas de milhares de fórmulas satisfatórias. Os pontos C4D9 e C5D13 são difíceis. O ponto C5D16 é conjecturado para existir. Uma instância aleatória de cinco cores do décimo sexto grau provaria a conjectura.