Los resultados que muestran la existencia / no existencia de gráficos finitos con propiedades computables específicas implican ciertos resultados de complejidad

¿Hay resultados conocidos que demuestren que la existencia (o la no existencia) de gráficos finitos con propiedades computables específicas implican ciertos resultados de complejidad (como P = NP)?

Aquí hay un resultado completamente hipotético : si existe un gráfico finito con bordes distingos A, B, C y D, de modo que todas las coincidencias máximas contengan todos A, B, C y D, o no contengan ninguno de A, B, C y D , entonces P = NP.

Lipton probó un resultado de este tipo "Al demostrar que un gráfico no tiene una camarilla grande: una conexión con la teoría de Ramsey" . Conecta conjeturas de límite inferior con resultados puramente teóricos de gráficos, mostrando que si no está contenido en c o N T I M E ( n O ( log n ) ) / ( log log n ) , entonces la inaplicabilidad de M A X - C L I Q U $NP$$coNTIME(n^{O(\log n)})/(\log \log n)$$MAX-CLIQUE$implica que hay gráficas con propiedades ordenadas de la teoría de Ramsey. (Consulte el documento para ver las definiciones). No tengo idea de si se ha realizado algún progreso para probar si tales gráficos existen o no.

Lo siento, me encontré con esta pregunta de 1 año solo ahora ...

De hecho, hay muchos resultados que muestran que los gráficos explícitos con algunas propiedades implican límites inferiores fuertes para las funciones booleanas. Digamos, los gráficos de alta dimensión afín o proyectiva implican límites inferiores fuertes para fórmulas y programas de ramificación. También hay medidas de gráficos "más simples", buenos límites inferiores en los que tendría grandes consecuencias en la complejidad computacional. Déjame dibujar algunos de ellos.

$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$$K_{2,2}$$s(G)$

$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$$Star(G)\geq 2n-1$

$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$$Sym(G)$$Sym(G)=O(\log n)$$T$

Puede encontrar más detalles sobre cómo sucede todo esto aquí .

$f:{0,1}^n\rightarrow {0,1}^n$$O(n)$$O(\log n)$profundidad, algo que todavía estamos lejos de demostrar) bajo los supuestos de que ciertos tipos de gráficos, llamados superconcentradores, no existen. (Esta fue una pregunta asintótica, y no se trata solo de un gráfico). Sin embargo, más tarde demostró que existen (y de hecho tienen otros usos)

La respuesta es ciertamente "sí" si hablamos de familias de gráficos, en lugar de gráficos específicos. Por ejemplo, hay una conjetura de Mihail y Vazirani de que todos los gráficos politopales 0/1 son expansores de bordes buenos o muy buenos (es decir, que su expansión de bordes está limitada por debajo de 1 / polinomio (grado) o 1).

Si esto es cierto, existen algoritmos de aproximación de Monte Carlo de cadena de Markov aleatorizados eficientes para una serie de problemas combinatorios y de conteo abiertos a través de una estrategia de muestreo de Alon, Jerrum y Sinclair.

En una línea similar, si existen familias de gráficos politopales cuyo diámetro crece más rápido que cualquier polinomio en el número de facetas y grado de gráfico, entonces la programación lineal no puede resolverse en tiempo fuertemente polinómico a través de algoritmos de seguimiento de bordes.

Ampliando el comentario de Anand Kulkarni:

Supongamos que hay una máquina de Turing determinista M que reconoce SAT en tiempo polinómico. Entonces la relación de transición finita de M será una función. Sabemos de TM que reconocen SAT en tiempo polinómico, pero sus relaciones de transición no son funciones. Tenga en cuenta que la relación de transición es un gráfico dirigido bipartito con tuplas de (estado, símbolo de cinta) en una bipartición, tuplas de (estado, símbolo de cinta, movimiento) en la otra bipartición y arcos de pares a triples.

Entonces, trivialmente, si hay un dígrafo que es una función, entonces P = NP.

Por supuesto, esta no es una definición muy natural, ya que requiere maquinaria auxiliar para dar sentido al requisito de que cada ruta en el espacio de estado que alcanza el estado de aceptación tiene una longitud limitada por un polinomio en el tamaño de entrada. No es del todo obvio cómo se ve el conjunto de gráficos finitos que representan máquinas de Turing con límites de tiempo, o si estos gráficos tienen propiedades teóricas de gráficos interesantes.