Strong partial clones and the time complexity of SAT problems
Authors:
- Peter JonssonPJPeter Jonsson
- Victor LagerkvistVLVictor Lagerkvist
- Gustav NordhGNGustav Nordh
- Bruno ZanuttiniBZBruno Zanuttini
- 1 March 2017
- journal article
- research article
- Published by Elsevier in Journal of Computer and System Sciences
- Vol. 84, 52-78
Abstract
No abstract availableKeywords
Funding Information
- French National Research Agency (ANR-10-BLAN-0210)
- Swedish Research Council (2009-4431, 2012-3239)
- Swedish Research Council (2008-4675)
- DFG (622397)
This publication has 17 references indexed in Scilit:
- The complexity of homomorphism and constraint satisfaction problems seen from the other sideJournal of the ACM, 2007
- Which Problems Have Strongly Exponential Complexity?Journal of Computer and System Sciences, 2001
- Hard Tiling Problems with Simple TilesDiscrete & Computational Geometry, 2001
- On some closed classes in partial two-valued logicDiscrete Mathematics and Applications, 1994
- A low and a high hierarchy within NPJournal of Computer and System Sciences, 1983
- The algebras of partial functions and their invariantsCybernetics and Systems Analysis, 1981
- On the Structure of Polynomial Time ReducibilityJournal of the ACM, 1975
- Galois theory for post algebras. ICybernetics and Systems Analysis, 1972
- Galois theory for Post algebras. IICybernetics and Systems Analysis, 1969
- Closed systems of functions and predicatesPacific Journal of Mathematics, 1968