Proving completeness by logic

DOI10.1080/00207160412331296625MaRDI QIDQ4653719zbMATH OpenOpenAlexFDO

Authors Bruno Escoffier, Vangelis Th. Paschos

Publication date 7 March 2005

Published in International Journal of Computer Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1080/00207160412331296625

zbMATH Keywords

CompletenessMin-NPO-completenessNP-completenessReductionSAT

Mathematics Subject Classification ID

Complexity of computation (including implicit computational complexity) (03D15) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Descriptive complexity and finite models (68Q19)

Recommendations

• scientific article; zbMATH DE number 1301808
• Provability logic and the completeness principle
• Methods for proving completeness via logical reductions
• Deductive Completeness
• Completeness theory for propositional logics
• Completeness in Proof-Theoretic Semantics
• scientific article; zbMATH DE number 3857062
• On the completeness of propositional Hoare logic
• On the meaning of logical completeness
• On the Meaning of Logical Completeness

Cites work

• Optimization, approximation, and complexity classes

Cited in

(8)

• Provability logic and the completeness principle
• A brief proof of the full completeness of Shin's Venn diagram proof system
• Polynomial approximation: a structural and operational study. (Abstract of thesis)
• On the Meaning of Logical Completeness
• scientific article; zbMATH DE number 408812 (Why is no real title available?)
• A survey on the structure of approximation classes
• STACS 2004
• Theorem Proving in Higher Order Logics

This page was built for publication: Proving completeness by logic

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