A complexity gap for tree resolution
DOI10.1007/s00037-001-8194-yzbMath0994.03005MaRDI QIDQ1601038
Publication date: 17 June 2002
Published in: Computational Complexity (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/s00037-001-8194-y
satisfiability; propositional proof complexity; combinatorial principles; gap phenomenon; hard propositional tautologies; infinite mathematical theories; tree-resolution proofs
03B25: Decidability of theories and sets of sentences
03B35: Mechanization of proofs and logical operations
03B05: Classical propositional logic
68Q17: Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)
03C13: Model theory of finite structures
03F20: Complexity of proofs
Related Items