Batas Bawah untuk Frege dan Frege Diperpanjang

9

Wikipedia [1] menyatakan bahwa batas bawah paling dikenal untuk ukuran bukti Frege adalah kuadratik, dan bahwa tidak ada batas bawah superlinear yang diketahui untuk jumlah garis bukti Frege.

Pertanyaan:

1) Apa batas bawah paling dikenal untuk jumlah garis bukti Frege diperpanjang?

2) Apa batas bawah paling dikenal untuk ukuran bukti Frege diperpanjang? Apakah masih kuadratik seperti di Frege?

3) Frege Diperpanjang seperti Pohon dapat mensimulasikan Dge seperti Frege seperti dalam jumlah langkah polinomial. Apakah ada batas bawah superlinear untuk ukuran / jumlah garis pada Frege diperpanjang seperti pohon?

4) Apa tautologi yang mengarah pada batas bawah linier untuk jumlah garis dan batas bawah kuadratik untuk ukuran dalam bukti Frege sebagaimana dinyatakan di wikipedia?

Obs: Saya menyadari fakta bahwa untuk Frege dengan kedalaman konstan, kita memiliki batas ukuran yang lebih rendah dari urutan . Tapi saya benar-benar tertarik pada kekuatan penuh Frege dan Extended Frege.2Ω(n6−d)

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

proof-complexity memverifikasi
sumber

Jawaban:

13

¬2n⊤

3) Tidak sepenuhnya jelas bagi saya bagaimana tepatnya Anda mendefinisikan Frege diperpanjang seperti pohon (harus ada mekanisme yang memungkinkan penggunaan kembali aksioma ekstensi), tapi saya tidak mengetahui adanya batas bawah superlinear pada jumlah garis di treelike Frege atau sistem Frege diperpanjang.

Emil Jeřábek
sumber
1
Tidak bisakah Anda mendefinisikan Extended Frege sebagai Circuit Frege (dalam makalah APAL 2004 Anda)? Dan dengan demikian definisi Frege seperti rangkaian pohon langsung.
Iddo Tzameret
1
@Iddo: Saya bisa, tetapi saya juga bisa mendefinisikannya dalam beberapa cara lain, dan tidak sepenuhnya jelas jumlah garis mereka akan sama dalam rezim ketat ini (linier).
Emil Jeřábek
1
Juga, saya pikir bahwa untuk Frege diperpanjang ukuran batas bawah hanya linier dan bukan kuadrat, kan?
Iddo Tzameret
2
Tidak, itu yang ingin saya sampaikan. Batas bawah kuadrat berlaku untuk Frege diperpanjang, bahkan jika itu tidak umum dinyatakan seperti itu.
Emil Jeřábek
1
Saya pikir itu kuadrat hanya jika Anda menentukan ukuran Frege diperpanjang dengan menghitung jumlah subformula (berbeda). Tetapi ukuran sebenarnya adalah linear. Saya harus meninjau kembali buktinya ...
Iddo Tzameret