Graficar problemas con buena caracterización pero no se sabe que están en

Un problema de decisión tiene una buena caracterización si está en . Muchos problemas gráficos naturales tienen buenas caracterizaciones. Por ejemplo, el teorema de Kuratuwski ofrece una buena caracterización de los gráficos planos. El teorema de Konig ofrece una buena caracterización de gráficos bipartitos. El teorema de Tutte ofrece una buena caracterización de gráficos que tienen una correspondencia perfecta. El teorema de Euler ofrece una buena caracterización de los gráficos eulerianos. Todos estos problemas de reconocimiento tienen algoritmos de tiempo polinómico.$NP \cap coNP$

¿Existe un problema gráfico natural que tenga una buena caracterización pero no se sepa que está en ? Se agradecería un puntero a una encuesta de tales problemas.$P$

En una de mis entradas del blog , he mencionado cuatro problemas (Factoring, Juegos de paridad, estocásticas de juegos, un entramado de problemas) que se sabe que son en pero no sabe que en P .$NP \cap coNP$$P$

Los juegos de paridad y los juegos estocásticos se pueden considerar como "problemas gráficos".

También, El Bicliques Problema Dos está en . Este es un problema gráfico natural que no se sabe que es en P .$NP \cap coNP$$P$

Determinar el ganador de un "juego de paridad" es conocido por ser en , pero es un problema abierto en circulación ya sea en P . Ver por ejemplo,$NP\cap coNP$$P$

http://lovelace.thi.informatik.uni-frankfurt.de/~klauck/XOR.pdf

Sin embargo, tenga en cuenta que un juego de paridad se define mediante un gráfico dirigido anotado, por lo que es posible que no desee considerarlo un "problema de gráfico natural".

Kuperberg demostró recientemente que la anudación (de un diagrama de nudos dado) está en NP ∩ coNP , suponiendo que la hipótesis generalizada de Riemann es cierta. Un diagrama de nudos está lo suficientemente cerca de un gráfico que creo que esto cuenta como una respuesta a su pregunta.