Preguntas etiquetadas con proof-search

Si P = NP, ¿podríamos obtener pruebas de la Conjetura de Goldbach, etc.?

Esta es una pregunta ingenua, por mi experiencia; disculpas de antemano. La Conjetura de Goldbach y muchas otras preguntas no resueltas en matemáticas se pueden escribir como fórmulas cortas en cálculo de predicados. Por ejemplo, el artículo de Cook "¿Pueden las computadoras descubrir...

¿Un teorema de suma directa para la complejidad del espacio de la cláusula de resolución?

La resolución es un esquema para demostrar la insatisfacción de los CNF. Una prueba en resolución es una deducción lógica de la cláusula vacía para las cláusulas iniciales de la CNF. En particular, se puede inferir cualquier cláusula inicial, y de dos cláusulas A ∨ xA∨xA \lor x y B ∨ ¬ xB∨¬xB \lor...