El teorema de Robertson-Seymour dice que cualquier familia GG\mathcal G de gráficas menores cerradas puede caracterizarse por un número finito de menores prohibidos. ¿Existe algún algoritmo que para una entrada GG\mathcal G dé salida a los menores prohibidos o es indecidible? Obviamente, la...
Problema: Considere un número finito de estados de control (incluyendo un estado "inicial" y un estado "malo"), un número finito de variables enteras y para cada par ordenado de estados una relación de transición expresada en aritmética de Presburger. Decida si existe una invariante inductiva (=...
Respuesta aceptada La respuesta de Scott Aaronson ha sido "aceptada" (¡principalmente porque es la única respuesta!) Resumen de respuesta de una oración Las generalizaciones plausiblemente naturales de la pregunta P versus NP no son obviamente más fáciles de resolver que P versus NP en sí. Una...