The complexity of satisfaction problems in reverse mathematics

DOI10.3233/COM-150034zbMATH Open1326.03022arXiv1411.1592MaRDI QIDQ5261155FDOQ5261155

Authors: Ludovic Patey 

Publication date: 1 July 2015

Published in: Computability (Search for Journal in Brave)

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.

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

Recommendations

• The Complexity of Satisfaction Problems in Reverse Mathematics
• The complexity of satisfiability problems
• Publication:2762521
• The complexity of minimal satisfiability problems
• Mathematical Foundations of Computer Science 2005

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)

Cited In (4)

• Easy solutions for a hard problem? The computational complexity of reciprocals with quantificational antecedents
• Title not available (Why is that?)
• The Complexity of Satisfaction Problems in Reverse Mathematics
• On avoidability of formulas with reversal

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)