Limites inférieures pour Frege et Extended Frege

Wikipedia [1] déclare que la borne inférieure la plus connue pour la taille des preuves Frege est quadratique et qu'il n'y a pas de borne inférieure super-linéaire connue pour le nombre de lignes de preuves Frege.

Des questions:

1) Quelle est la borne inférieure la plus connue pour le nombre de lignes de preuves Frege étendues?

2) Quelle est la borne inférieure la plus connue pour la taille des preuves Frege étendues? Est-il toujours quadratique comme à Frege?

3) Frege étendu en forme d'arbre peut simuler Frege étendu en forme de DAG en un nombre polynomial d'étapes. Existe-t-il des bornes inférieures super-linéaires pour la taille / le nombre de lignes sur Frege étendu en forme d'arbre?

4) Quelles sont les tautologies qui conduisent à la borne inférieure linéaire pour le nombre de lignes et à la borne inférieure quadratique pour la taille dans les épreuves Frege comme indiqué sur wikipedia?

Obs: Je sais que pour Frege à profondeur constante, nous avons des bornes inférieures de taille de l'ordre de . Mais je suis vraiment intéressé par la pleine puissance Frege et Extended Frege. $2^{\Omega(n^{6^{-d}})}$

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

proof-complexity vérification
la source

Réponses:

1, 2, 4) Les limites inférieures les plus connues sur Frege étendu sont les mêmes que pour Frege: nombre linéaire de lignes et taille quadratique. Cela s'applique par exemple aux tautologies (fondamentalement, toute tautologie qui n'est pas une instance de substitution d'une tautologie plus courte, et dont la somme des longueurs de toutes les sous-formules est quadratique). Cela est prouvé dans l' arithmétique, la logique propositionnelle et la théorie de la complexité de Krajíček pour les systèmes de Frege, mais l'argument fonctionne également pour les systèmes de Frege étendus. $\neg^{2n}\top$

3) Je ne sais pas exactement comment vous définissez exactement Frege étendu semblable à un arbre (il doit y avoir un mécanisme permettant la réutilisation des axiomes d'extension), mais je ne connais aucune limite inférieure superlinéaire sur le nombre de lignes dans Freel treelike ou systèmes Frege étendus.

Emil Jeřábek
la source

Ne pouvez-vous pas définir Extended Frege comme Circuit Frege (dans votre article APAL 2004)? Et donc la définition d'arbre comme circuit Frege est immédiate.

Iddo Tzameret

@Iddo: Je peux, mais je peux aussi le définir de plusieurs autres façons, et il n'est pas tout à fait clair que leur nombre de lignes sera le même dans ce régime strict (linéaire).

Emil Jeřábek

De plus, je pense que pour Frege étendu, la limite inférieure de la taille n'est que linéaire et non quadratique, non?

Iddo Tzameret

Non, c'est le point que j'essaie de faire passer. La borne inférieure quadratique vaut pour Frege étendu, même si ce n'est pas communément indiqué de cette façon.

Emil Jeřábek

Je pensais que ce n'est quadratique que si vous définissez la taille de Frege étendu en comptant le nombre de sous-formules (distinctes). Mais la taille réelle est linéaire. Je vais devoir revoir la preuve alors ...

Iddo Tzameret