ALOGTIME and a conjecture of S. A. Cook

DOI10.1007/BF01531023zbMath0865.03029WikidataQ123220857 ScholiaQ123220857MaRDI QIDQ1353980

Peter Clote

Publication date: 13 May 1997

Published in: Annals of Mathematics and Artificial Intelligence (Search for Journal in Brave)

zbMATH Keywords

propositional calculus; NC; resolution proof; Frege proofs; parallel complexity classes; free variable equational logic

Mathematics Subject Classification ID

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

• 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