
We investigate the computational complexity of the exact satisfiability problem (XSAT) restricted to certain subclasses of linear CNF formulas. These classes are defined through restricting the number of occurrences of variables and are therefore interesting because the complexity status does not follow from Schaefer’s theorem [14,7]. Specifically we prove that XSAT remains NP-complete for linear formulas which are monotone and all variables occur exactly l times. We also present some complexity results for exact linear formulas left open in [9]. Concretely, we show that XSAT for this class is NP-complete, in contrast to SAT or NAE-SAT. This can also be established when clauses have length at least k, for fixed integer k≥3. However, the XSAT-complexity for exact linear formulas with clause length exactly k remains open, but we provide its polynomial-time behaviour at least for every positive integer k≤6.
| selected citations These citations are derived from selected sources. This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | 0 | |
| popularity This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network. | Average | |
| influence This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | Average | |
| impulse This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network. | Average |
