|
| << vorige |
Tijdschrift beschrijving
Alle jaargangen van het bijbehorende tijdschrift
Alle afleveringen van het bijbehorende jaargang
Alle artikelen van de bijbehorende aflevering
Details van artikel 4 van 4 gevonden artikelen
| Titel: |
The complexity of satisfaction problems in reverse mathematics |
| Auteur: |
Patey, Ludovic |
| Verschenen in: |
Computability |
| Paginering: | Jaargang 4 (2015) nr. 1 pagina's 69-84 |
| Jaar: |
2015-02-19 |
| Inhoud: |
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 RCA0 or equivalent to WKL0. 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. |
| Uitgever: |
IOS Press |
| Bronbestand: |
Elektronische Wetenschappelijke Tijdschriften |
Details van artikel 4 van 4 gevonden artikelen
| << vorige |
Toegankelijkheidsverklaring