Frege proof system and TNC°
From MaRDI portal
Publication:4212930
DOI10.2307/2586859zbMath0959.03047OpenAlexW2575470425MaRDI QIDQ4212930
Publication date: 2 May 2001
Published in: The Journal of Symbolic Logic (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.2307/2586859
first-order systempropositional calculusFrege proof systemuniform proofextended Frege proof systemcomputational complexity class \(\text{NC}^1\).
First-order arithmetic and fragments (03F30) Classical propositional logic (03B05) Structure of proofs (03F07) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Complexity of proofs (03F20)
Cites Work
- Propositional consistency proofs
- RSUV isomorphisms for TAC\(^ i\), TNC\(^ i\) and \(TLS\)
- ALOGTIME and a conjecture of S. A. Cook
- \(S^ i_ 3\) and \(\overset\circ V^ i_ 2(BD)\)
- Propositional proof systems, the consistency of first order theories and the complexity of computations
- An Optimal Parallel Algorithm for Formula Evaluation
This page was built for publication: Frege proof system and TNC°