The complexity of the falsifiability problem for pure implicational formulas

DOI10.1016/S0166-218X(99)00036-0MaRDI QIDQ5917958zbMATH OpenFDO

Authors Peter Heusch

Publication date 17 January 2000

Published in Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/S0166-218X(99)00036-0

zbMATH Keywords

falsifiability

Mathematics Subject Classification ID

Data structures (68P05) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Nonnumerical algorithms (68W05)

Recommendations

• The complexity of the falsifiability problem for pure implicational formulas
• An algorithm for the class of pure implicational formulas
• The complexity of propositional implication
• scientific article; zbMATH DE number 3978379
• A note on the computational complexity of the pure classical implication calculus

Cites work

• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 3045411 (Why is no real title available?)
• Nested satisfiability
• Polynomially solvable satisfiability problems

Cited in

(6)

• A note on the computational complexity of the pure classical implication calculus
• An algorithm for the class of pure implicational formulas
• scientific article; zbMATH DE number 1453038 (Why is no real title available?)
• The complexity of the falsifiability problem for pure implicational formulas
• On the expressive power of implication in classical propositional logic
• The complexity of propositional implication

This page was built for publication: The complexity of the falsifiability problem for pure implicational formulas

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5917958)