Problemas gráficos com boa caracterização, mas não conhecidos por

Um problema de decisão tem boa caracterização se estiver em . Muitos problemas gráficos naturais têm boas caracterizações. Por exemplo, o Teorema de Kuratuwski fornece uma boa caracterização de gráficos planares. O Teorema de Konig fornece uma boa caracterização de gráficos bipartidos. O Teorema de Tutte fornece uma boa caracterização de gráficos que têm correspondência perfeita. O Teorema de Euler fornece uma boa caracterização dos gráficos eulerianos. Todos esses problemas de reconhecimento têm algoritmos de tempo polinomial.$NP \cap coNP$

Existe um problema gráfico natural que tenha boa caracterização, mas que não seja conhecido em ? Um ponteiro para uma pesquisa de tais problemas seria apreciado.$P$

Em um dos meus posts , eu mencionei quatro problemas (factoring, paridade Jogos, Jogos estocásticos, uma treliça problema) que são conhecidos por estar em , mas não conhecidos para a .$NP \cap coNP$$P$

Jogos de paridade e jogos estocásticos podem ser considerados como "problemas gráficos".

Além disso, o problema das duas bicicletas está em . Este é um problema gráfico natural que não é conhecido por ser em .$NP \cap coNP$$P$

$NP\cap coNP$$P$

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

Observe, no entanto, que um jogo de paridade é definido por um gráfico direcionado anotado; portanto, você pode não querer considerá-lo um "problema natural de gráfico".

Kuperberg provou recentemente que o nó (de um dado diagrama de nós) está em NP ∩ coNP , assumindo que a hipótese generalizada de Riemann seja verdadeira. Um diagrama de nó é próximo o suficiente de um gráfico, que acho que isso conta como resposta à sua pergunta.