ALOGTIME and a conjecture of S. A. Cook

DOI10.1007/BF01531023zbMath0865.03029OpenAlexW3157713018WikidataQ123220857 ScholiaQ123220857MaRDI QIDQ1353980

Peter Clote

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

zbMATH Keywords

propositional calculusNCresolution proofFrege proofsparallel complexity classesfree variable equational logic

Mathematics Subject Classification ID

Mechanization of proofs and logical operations (03B35) Complexity of computation (including implicit computational complexity) (03D15) Classical propositional logic (03B05) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Complexity of proofs (03F20)

Related Items (5)

The equivalence of theories that characterize ALogTime ⋮ Quantified propositional calculus and a second-order theory for NC\(^{\text \textbf{1}}\) ⋮ On theories of bounded arithmetic for \(\mathrm{NC}^1\) ⋮ Frege proof system and TNC° ⋮ Frege proof system and TNC°

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• 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

This page was built for publication: ALOGTIME and a conjecture of S. A. Cook