Frege proof system and TNC°

DOI10.2307/2586859zbMath0959.03047OpenAlexW2575470425MaRDI QIDQ4212930

Gaisi Takeuti

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

zbMATH Keywords

first-order systempropositional calculusFrege proof systemuniform proofextended Frege proof systemcomputational complexity class \(\text{NC}^1\).

Mathematics Subject Classification ID

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°