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

9

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 pruebas de Frege extendidas?

2) ¿Cuál es el límite inferior más conocido para el tamaño de las pruebas de Frege extendidas? ¿Sigue siendo cuadrático como en Frege?

3) La Frege Extendida tipo árbol puede simular la Frege extendida tipo DAG en un número polinómico de pasos. ¿Hay límites inferiores superlineales para el tamaño / número de líneas en Frege extendido en forma de árbol?

4) ¿Cuáles son las tautologías que conducen al límite inferior lineal para el número de líneas y al límite inferior cuadrático para el tamaño en las pruebas de Frege como se indica en wikipedia?

Obs: Soy consciente del hecho de que para Frege de profundidad constante tenemos límites inferiores de tamaño del orden de . Pero estoy realmente interesado en Frege a plena potencia y Frege Extendido.2Ω(n6−d)

[1] https://en.wikipedia.org/wiki/Frege_system

proof-complexity verificar
fuente

Respuestas:

13

¬2n⊤

3) No estoy del todo claro para mí cómo define exactamente la Frege extendida en forma de árbol (tiene que haber un mecanismo que permita la reutilización de los axiomas de extensión), pero no conozco ningún límite inferior superlineal en el número de líneas en Frege en forma de árbol o Sistemas Frege extendidos.

Emil Jeřábek
fuente
1
¿No puede definir Extended Frege como Circuit Frege (en su documento APAL 2004)? Y así, la definición de Frege de árbol como circuito es inmediata.
Iddo Tzameret
1
@ Iddo: puedo, pero también puedo definirlo de varias otras maneras, y no está del todo claro si su número de líneas será el mismo en este régimen estricto (lineal).
Emil Jeřábek
1
Además, creo que para Frege extendida, el tamaño del límite inferior es solo lineal y no cuadrático, ¿verdad?
Iddo Tzameret
2
No, ese es el punto que estoy tratando de comunicar. El límite inferior cuadrático se mantiene para Frege extendido, incluso si no se dice comúnmente de esa manera.
Emil Jeřábek
1
Pensé que es cuadrático solo si define el tamaño de Frege extendido contando el número de subformulas (distintas). Pero el tamaño real es lineal. Tendré que revisar la prueba entonces ...
Iddo Tzameret