The complexity of satisfaction problems in reverse mathematics

DOI10.3233/COM-150034MaRDI QIDQ5261155zbMATH OpenFDO

Authors Ludovic Patey

Publication date 1 July 2015

Published in Computability (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1411.1592

zbMATH Keywords

satisfiabilitydichotomyreverse mathematicsRamsey's theorem

Mathematics Subject Classification ID

Foundations of classical theories (including reverse mathematics) (03B30) Second- and higher-order arithmetic and fragments (03F35)

Abstract: Satisfiability problems play a central role in computer science and engineering as a general framework for studying the complexity of various problems. Schaefer proved in 1978 that truth satisfaction of propositional formulas given a language of relations is either NP-complete or tractable. We classify the corresponding satisfying assignment construction problems in the framework of reverse mathematics and show that the principles are either provable over RCA or equivalent to WKL. We formulate also a Ramseyan version of the problems and state a different dichotomy theorem. However, the different classes arising from this classification are not known to be distinct.

Recommendations

• The Complexity of Satisfaction Problems in Reverse Mathematics
• The complexity of satisfiability problems
• scientific article; zbMATH DE number 1688380
• The complexity of minimal satisfiability problems
• Mathematical Foundations of Computer Science 2005

Cited in

(4)

• On avoidability of formulas with reversal
• Easy solutions for a hard problem? The computational complexity of reciprocals with quantificational antecedents
• scientific article; zbMATH DE number 6415494 (Why is no real title available?)
• The Complexity of Satisfaction Problems in Reverse Mathematics

This page was built for publication: The complexity of satisfaction problems in reverse mathematics

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