Pytania oznaczone «proof-complexity»

Złożoność dowodu jest najbardziej podstawowym obszarem teorii złożoności obliczeniowej. Ostatecznym celem tego obszaru jest udowodnienie , co oznacza, że ​​żaden z proverów nie może dać dowodu na niezadowolenie danej formuły wejściowej. N.P.≠ c o NP.N.P.≠dooN.P.NP\neq coNP Wykres jest jednym z...

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...

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...