Untergrenzen für Frege und Extended Frege

9

Wikipedia [1] gibt an, dass die bekannteste Untergrenze für die Größe von Frege-Beweisen quadratisch ist und dass keine superlinearen Untergrenzen für die Anzahl der Zeilen von Frege-Beweisen bekannt sind.

Fragen:

1) Was ist die bekannteste Untergrenze für die Anzahl der Zeilen erweiterter Frege-Beweise?

2) Was ist die bekannteste Untergrenze für die Größe erweiterter Frege-Proofs? Ist es noch quadratisch wie in Frege?

3) Tree-like Extended Frege kann DAG-like Extended Frege in einer polynomiellen Anzahl von Schritten simulieren. Gibt es superlineare Untergrenzen für Größe / Anzahl der Linien auf baumartigen erweiterten Frege?

4) Welche Tautologien führen zur linearen Untergrenze für die Anzahl der Linien und zur quadratischen Untergrenze für die Größe in Frege-Proofs, wie in Wikipedia angegeben?

Obs: Mir ist bewusst, dass wir für Frege mit konstanter Tiefe Größenuntergrenzen in der Größenordnung von . Aber ich interessiere mich wirklich für Frege mit voller Leistung und Extended Frege.2Ω(n6d)

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

Überprüfung
quelle

Antworten:

13

¬2n

3) Mir ist nicht ganz klar, wie genau Sie baumartig erweiterte Frege definieren (es muss einen Mechanismus geben, der die Wiederverwendung von Erweiterungsaxiomen ermöglicht), aber mir sind keine superlinearen Untergrenzen für die Anzahl der Linien in baumartigen Frege oder bekannt erweiterte Frege-Systeme.

Emil Jeřábek
quelle
1
Können Sie Extended Frege nicht als Circuit Frege definieren (in Ihrem APAL 2004-Dokument)? Und so ist die baumartige Frege-Definition unmittelbar.
Iddo Tzameret
1
@Iddo: Ich kann, aber ich kann es auch auf verschiedene andere Arten definieren, und es ist nicht ganz klar, dass die Anzahl der Zeilen in diesem strengen Regime (linear) gleich sein wird.
Emil Jeřábek
1
Ich denke auch, dass für Extended Frege die Größenuntergrenze nur linear und nicht quadratisch ist, oder?
Iddo Tzameret
2
Nein, das ist der Punkt, den ich vermitteln möchte. Die quadratische Untergrenze gilt für Extended Frege, auch wenn dies nicht allgemein so angegeben wird.
Emil Jeřábek
1
Ich dachte, es ist nur quadratisch, wenn Sie die Größe der erweiterten Frege definieren, indem Sie die Anzahl der (unterschiedlichen) Unterformeln zählen. Die tatsächliche Größe ist jedoch linear. Ich muss den Beweis dann noch einmal
überprüfen