Pytania oznaczone «proof-complexity»

9
Intuicja za systemami dowodowymi

Próbuję zrozumieć artykuł na temat p-Optimal Proof Systems and Logic for PTIME . W artykule jest pojęcie nazywane systemami dowodowymi i nie rozumiem intencji: Σ = { 0 , 1 }Σ={0,1}\Sigma = \{0,1\} ... Identyfikujemy problemy z podzbiorami w .QQQΣ∗Σ∗\Sigma^* Myślę, że intencją jest to, że...

9
Dolne granice dla Frege i Extended Frege

Wikipedia [1] stwierdza, że ​​najlepiej znana dolna granica dla wielkości dowodów Frege jest kwadratowa i że nie ma znanych dolnych granic superliniowych dla liczby linii dowodów Frege. Pytania: 1) Jaka jest najbardziej znana dolna granica dla liczby linii rozszerzonych proofów Frege? 2) Jaka...