Informações comuns sobre a complexidade hipotética de problemas gráficos

Me deparei com dois exemplos de dureza hipotética de alguns problemas gráficos. Dureza hipotética significa que refutar algumas conjecturas implicaria a completude NP do respectivo problema gráfico. Por exemplo, a conjectura de Barnette afirma que todo gráfico bipartido cúbico planar cúbico de 3 conexões é hamiltoniano. Feder e Subi provaram que refutar a conjectura implicaria a completude da PN do problema do ciclo hamiltoniano em gráficos da classe da conjectura.

A conjectura de 5 fluxos de Tutte afirma que todo gráfico sem ponte tem um fluxo 5 em lugar nenhum zero. Kochol mostrou que, se a conjectura é falsa, o problema de determinar se um gráfico cúbico admite um fluxo 5 em lugar nenhum zero é NP-completo .

Existem insights comuns sobre as conjecturas acima que explicam a hipotética completude do NP dos problemas correspondentes do gráfico? Existem outros exemplos de complexidade hipotética no sentido acima?

PS Isso foi publicado no MathoverFlow sem obter resposta.

Aqui estão duas referências para a segunda parte da sua pergunta.

O artigo [1] aborda certos tipos de colorabilidade de gráficos esparsos com determinada circunferência . Para cada fixo , eles mostram que o problema de decisão associado é trivial (todos os gráficos da classe têm uma coloração) ou NP-completo. Mas determinar qual é o valor limite de permanece um difícil problema em aberto! Edit: Um dos problemas considerados está relacionado à conjectura de Jaeger, que todo gráfico planar da circunferência admite um homomorfismo em$g$$g$$g$
$4k$$C_{2k+1}$. É mostrado em [1] que qualquer contra-exemplo fornece diretamente uma prova de dureza. (Existe uma conjectura semelhante de Klostermeyer e Zhang para a circunferência estranha.) Para os outros problemas considerados em [1], não há conjectura oficial, mas para qualquer suposição sobre o valor-limite correto que alguém pode fazer, se se provar falso por um contra-exemplo, este último implica diretamente uma prova de dureza correspondente.$g$

Na introdução do artigo acima citado, também é mencionado o seguinte resultado interessante sobre o SAT [2]. Está provado lá que, para todo , existe uma função tal que -SAT (ou seja, -SAT onde cada variável ocorre vezes) é trivial, mas -SAT é NP-completo. (O valor exato de parece desconhecido, embora seja feita uma estimativa.)$k$$f(k)$$(k,f(k))$$k$$f(k)$$(k,f(k)+1)$$f(k)$

[1] L. Esperet, M. Montassier, P. Ochem e A. Pinlou. Uma dicotomia de complexidade para a coloração de gráficos esparsos. Journal of Graph Theory 73: 85-102, 2012. link + PDF no site de um autor

[2] J. Kratochvil, P. Savicky e Zs. Tuza. Mais uma ocorrência de variáveis ​​faz com que a satisfação salte de trivial para NP-complete. Jornal SIAM on Computing 22: 203-210, 1993. link

Existem insights comuns sobre as conjecturas acima que explicam a hipotética completude do NP dos problemas correspondentes do gráfico?

Na minha opinião, há uma clara visão comum na direção oposta: se as conjecturas são verdadeiras, os problemas correspondentes não são NP completos e acabam sendo triviais em ambos os casos (eles alternam de NPC para ).$O(1)$

E o insight comum é que os problemas naturais, o ciclo hamiltoniano e o fluxo zero em nenhum lugar nos gráficos gerais, são "estruturados e poderosos" o suficiente para "simular" com eficiência o traço de uma máquina de Turing (à Cook-Levin). Então você começa a adicionar mais e mais restrições até não ter "poder computacional".

Para mim, é como adicionar mais e mais restrições no gráfico de transição de uma máquina de Turing (ou no dispositivo de fita de leitura / gravação) até obter algo trivial como "o gráfico de transição não contém um ciclo".

Existem outros exemplos de complexidade hipotética no sentido acima?

Como (provavelmente) "caso resolvido", posso trazer minha experiência relacionada ao problema de rolar uma matriz sobre uma placa rotulada .

Há alguns anos atrás, não se sabia se as placas totalmente rotuladas podem conter dois ciclos de Hamiltonain distintos ( conjecturas de rolagem exclusiva foram estabelecidas para todas as placas com comprimentos laterais no máximo 8). Domotor P. (usuário domotorp aqui) e eu (independentemente) provamos que tais painéis existem e a conjectura é falsa (... observe que Joseph O'Rourke ainda não atualizou sua página :-).

Então, usando esse fato, pude provar que rolar uma matriz em uma placa totalmente rotulada com orifícios é NP-completo (a caixa sem orifícios ainda está aberta); embora este seja um resultado não publicado.