ALOGTIME and a conjecture of S. A. Cook
From MaRDI portal
Publication:1353980
DOI10.1007/BF01531023zbMath0865.03029WikidataQ123220857 ScholiaQ123220857MaRDI QIDQ1353980
Publication date: 13 May 1997
Published in: Annals of Mathematics and Artificial Intelligence (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/bf01531023
propositional calculus; NC; resolution proof; Frege proofs; parallel complexity classes; free variable equational logic
03B35: Mechanization of proofs and logical operations
03D15: Complexity of computation (including implicit computational complexity)
03B05: Classical propositional logic
68Q15: Complexity classes (hierarchies, relations among complexity classes, etc.)
03F20: Complexity of proofs
Related Items
On theories of bounded arithmetic for \(\mathrm{NC}^1\), The equivalence of theories that characterize ALogTime, Quantified propositional calculus and a second-order theory for NC\(^{\text \textbf{1}}\), Frege proof system and TNC°
Cites Work
- On uniform circuit complexity
- Weak Second‐Order Arithmetic and Finite Automata
- Propositional proof systems, the consistency of first order theories and the complexity of computations
- A taxonomy of problems with fast parallel algorithms
- Polynomial size proofs of the propositional pigeonhole principle
- The relative efficiency of propositional proof systems
- Expressibility and Parallel Complexity
- Unnamed Item
- Unnamed Item
- Unnamed Item