Preguntas etiquetadas con proof-complexity

9
Límites más bajos para Frege y Frege extendido

Wikipedia [1] afirma que el límite inferior más conocido para el tamaño de las pruebas de Frege es cuadrático, y que no hay límites inferiores superlineales conocidos para el número de líneas de pruebas de Frege. Preguntas: 1) ¿Cuál es el límite inferior más conocido para el número de líneas de...