Exemplos de transições de fase de dureza

Suponha que tenhamos um problema parametrizado por um parâmetro com valor real p que seja "fácil" de resolver quando e "rígido" quando p = p 1 para alguns valores p 0 , p $p=p_0$$p=p_1$$p_0$$p_1$ .

Um exemplo é contar configurações de rotação nos gráficos. Contando cores adequadas ponderadas, conjuntos independentes, os subgráficos eulerianos correspondem às funções de partição dos modelos hardcore, Potts e Ising, respectivamente, fáceis de aproximar para "alta temperatura" e difíceis para "baixa temperatura". Para MCMC simples, a transição de fase de dureza corresponde a um ponto no qual o tempo de mistura salta de polinomial para exponencial ( Martineli, 2006 ).

Outro exemplo é a inferência em modelos probabilísticos. Nós "simplificamos" um modelo dado usando combinação 1 - p , p com um modelo "todas as variáveis ​​são independentes". Para p = 1, o problema é trivial, para p = 0 é intratável e o limiar de dureza está em algum ponto intermediário. Para o método de inferência mais popular, o problema se torna difícil quando o método não converge, e o ponto em que ocorre corresponde à transição de fase (no sentido físico) de uma determinada distribuição de Gibbs ( Tatikonda, 2002 ).$1-p$$p$$p=1$$p=0$

Quais são outros exemplos interessantes de "salto" de dureza, pois alguns parâmetros contínuos são variados?

Motivação: ver exemplos de outra "dimensão" de dureza além do tipo de gráfico ou tipo de lógica

Na aproximação padrão do pior caso, existem muitos limiares acentuados, pois o fator de aproximação varia.

Por exemplo, para o 3LIN, satisfazendo tantas equações lineares booleanas dadas em 3 variáveis ​​cada, existe um algoritmo de aproximação de atribuição aleatória simples para a aproximação 1/2, mas qualquer aproximação melhor que alguma t = 1/2 + o (1) já está tão difícil quanto o SAT exato (conjecturado para exigir tempo exponencial).

Não sei exatamente se esse é o tipo de problema que você estava procurando, mas a transição de fase dos problemas do NP-Complete é um fenômeno (agora) bem conhecido. Veja os artigos de Brian Hayes "Não consigo obter satisfação" sobre a transição da fase 3-SAT e "O problema mais fácil" sobre a transição da fase de partição numérica, para alguns artigos populares sobre o assunto.

Selman e Kirkpatrick foram os primeiros a mostrar numericamente que a transição de fase para o 3-SAT ocorreu quando a proporção de cláusulas para variáveis ​​estava em torno de 4,3.

Gent e Walsh foram os primeiros a mostrar numericamente que a transição de fase para o Problema da Partição Numérica aconteceu quando a proporção de bits para o comprimento da lista era de aproximadamente 1. Mais tarde, isso foi comprovado analiticamente por Borgs, Chayes e Pittel .

O vendedor ambulante, a coloração de gráfico, o ciclo hamiltoniano, entre outros, também parecem ter transições de fase para uma parametrização adequada da criação da instância do problema. Eu acho que é seguro dizer que é comum acreditar que todos os problemas do NP-Complete exibem uma transição de fase para uma parametrização adequada.

Associado a (alguns) modelos de ruído para computação quântica, há um valor limite para o nível de ruído, acima do qual os portões ruidosos podem ser simulados pelos portões de Clifford, de modo que os processos de computação quântica se tornem eficientemente simuláveis. Para começar, consulte Plenio e Virmani, Limites superiores nos limites de tolerância a falhas de computadores quânticos ruidosos baseados em Cliir r (arXiv: 0810.4340v1).

Modelos solucionáveis ​​como este nos informam sobre um problema prático onipresente: para um sistema quântico físico especificado em contato com um reservatório térmico (possivelmente em temperatura zero), são os níveis de ruído associados a esse reservatório térmico abaixo ou acima do limiar para uma simulação eficiente com métodos clássicos. Recursos? Nesse último caso, quais algoritmos de simulação são ótimos?

$k$$k$$k$

$f(k)$$k$$f(k)$$2^k$$k$$1 \le f(k) < 2^k$

$k$$n$$k$$f(k)/2^k$

$f(k)$$f(k)+1$

• Jan Kratochvíl, Petr Savický e Zsolt Tuza, Mais uma ocorrência de variáveis ​​faz com que a satisfação salte de trivial para NP-Complete , SIAM J. Comput. 22 (1) 203-210, 1993. doi: 10.1137 / 0222015

$f(k)$$f(k) = \Theta(2^k/k)$

• Heidi Gebauer, Reprovação da conjectura de vizinhança com implicações no SAT , Combinatorica 32 (5) 573–587, 2012. doi: 10.1007 / s00493-012-2679-y (pré - impressão)
• Heidi Gebauer, Tibor Szabó, Gábor Tardos, O lema local está apertado para o SAT , SODA 2011.