Resultados mostrando a existência / não existência de gráficos finitos com propriedades computáveis ​​específicas implicam certos resultados de complexidade

Existem resultados conhecidos mostrando que a existência (ou não) de gráficos finitos com propriedades computáveis ​​específicas implica certos resultados de complexidade (como P = NP)?

Aqui está um resultado completamente hipotético : Se existe um gráfico finito com arestas distintas, A, B, C e D, de modo que todas as correspondências máximas contenham todos A, B, C e D ou nenhuma A, B, C e D , então P = NP.

Um resultado desse tipo foi provado por Lipton "Ao provar que um gráfico não tem grande clique: uma conexão com a teoria de Ramsey" . Ele conecta conjecturas de limite inferior com resultados puramente gráficos, mostrando que, se não estiver contido em , a inadequação do implica que existem gráficos com boas propriedades teóricas de Ramsey. (Veja o documento para obter definições.) Não tenho idéia se houve algum progresso para provar se esses gráficos realmente existem ou não.c o N T I M E ( n O ( log n ) ) / ( log log n ) M A X - C L I Q U $NP$$coNTIME(n^{O(\log n)})/(\log \log n)$$MAX-CLIQUE$

Desculpe, me deparei com essa pergunta de 1 ano apenas agora ...

De fato, existem muitos resultados mostrando que gráficos explícitos com algumas propriedades implicam limites inferiores fortes para funções booleanas. Digamos, gráficos de alta dimensão afim ou projetiva implicam fortes limites inferiores para fórmulas e programas de ramificação. Existem também medidas "mais simples" de gráficos, bons limites inferiores nos quais teriam grandes consequências na complexidade computacional. Deixe-me esboçar alguns deles.

Veja os gráficos como conjuntos de arestas. Seja o menor número modo que possa ser escrito como uma interseção dos gráficos , cada um dos quais é uma união de bicliques (gráficos completos bipartidos). A contagem fácil mostra que para quase todos os gráficos bipartidos. Mas, pelos resultados de Valiant, todo gráfico bipartido explícito (mais exatamente, uma sequência de gráficos) com para uma constante$s(G)$$s$$G$$\leq s$$\leq s$$s(G)\geq n^{1/2}$$n\times n$$G$$s(G)\geq n^c$$c>0$resolveria um problema antigo: daria uma função booleana que não pode ser calculada por um circuito log-depth de tamanho linear. É conjecturado que gráficos densos sem tenham grandes .$K_{2,2}$$s(G)$

Melhor ainda, seja o menor número de operações união e interseção fanin- suficientes para gerar começando com estrelas completas (gráficos do tipo ou ). A contagem mostra que a maioria dos gráficos possui . Mas qualquer com para uma constante daria uma função booleana explícita que requer circuitos de tamanho exponencial! Se o gráfico tiver dimensão com , mesmo uma limite inferior$Star(G)$$2$$G$$K_{1,n}$$K_{n,1}$$Star(G)=\Omega(n^2/\log n)$$G$$Star(G)\geq (4+c)n$$c>0$$m\times n$$m=o(n)$$Star(G)\geq (2+c)n$teria as mesmas consequências. O melhor que podemos mostrar até agora é . $Star(G)\geq 2n-1$

Seja o menor número para o qual exista um subconjunto e uma sequência de bicliques tais que se o número de bicliques contendo pertence à . Novamente, a contagem fornece para a maioria dos gráficos. Mas, pelos resultados de Yao, Beigel e Tarui, qualquer gráfico explícito com maior que nos daria uma função booleana fora do . Aviso: ser "combinatoriamente complicado" por si só não implica grandes$Sym(G)$$t$$T\subseteq\{0,1,\ldots,t\}$$t$$(u,v)\in G$$(u,v)$$T$$Sym(G)\geq n/2$$Sym(G)$$2^{poly(\ln\ln n)}$$ACC$S y m ( G ) = O ( log n ) $Sym(G)$: existem fortemente gráficos de Ramsey para os quais , mesmo que = conjunto de números ímpares.$Sym(G)=O(\log n)$$T$

Mais detalhes sobre como tudo isso acontece podem ser encontrados aqui .

Um exemplo clássico foi de Valiant (não conheço a referência, mas acho que isso está descrito no livro de Hoory, Linial e Wigderson sobre gráficos de expansão ). Valiant mostrou um limite inferior explícito (acho que uma certa função explícita não possui um circuito de tamanho e profundidade - algo que ainda estamos longe de provar) sob o pressuposto de que certos tipos de gráficos, chamados superconcentradores, não existem. (Essa era uma pergunta assintótica, e não apenas um gráfico.) No entanto, mais tarde ele mostrou que elas existem (e de fato têm outros usos). O ( n ) O ( log n $f:{0,1}^n\rightarrow {0,1}^n$$O(n)$$O(\log n)$

A resposta é certamente "sim" se falamos sobre famílias de gráficos, em vez de gráficos específicos. Por exemplo, há uma conjectura de Mihail e Vazirani de que todos os gráficos politópicos 0/1 são bons ou muito bons expansores de borda (ou seja, que sua expansão de borda é delimitada abaixo por 1 / polinômio (grau) ou 1).

Se isso for verdade, existem algoritmos de aproximação de Monte Carlo, aleatórios e eficientes, aleatórios em cadeia de Markov para vários problemas combinatórios e de contagem abertos por meio de uma estratégia de amostragem de Alon, Jerrum e Sinclair.

Do mesmo modo, se existem famílias de gráficos politópicos cujo diâmetro cresce mais rápido do que qualquer polinômio no número de facetas e no grau do gráfico, a programação linear não pode ser resolvida em tempo fortemente polinomial por meio de algoritmos de seguimento de arestas.

Expandindo o comentário de Anand Kulkarni:

Suponha que exista uma máquina de Turing determinística M que reconheça SAT em tempo polinomial. Então a relação de transição finita de M será uma função. Conhecemos MTs que reconhecem SAT em tempo polinomial, mas suas relações de transição não são funções. Observe que a relação de transição é um gráfico direcionado bipartido com tuplas de (estado, símbolo de fita) em uma bipartição, tuplas de (estado, símbolo de fita, movimento) na outra bipartição e arcos de pares para triplos.

Tão trivialmente, se houver um dígrafo que seja uma função, então P = NP.

Obviamente, essa não é uma definição muito natural, pois exige que as máquinas auxiliares dêem sentido ao requisito de que todo caminho no espaço de estados que atinja o estado de aceitação tenha o comprimento limitado por um polinômio no tamanho da entrada. Não é de todo óbvio a aparência do conjunto de gráficos finitos que representam as máquinas de Turing com limite de politêmia ou se esses gráficos têm propriedades teóricas dos gráficos interessantes.