18 citations · 79 across the 28 of their papers we have counts for
Showing cs.CCShow all
2 papers · 1 filter
cs.CC2019★ 2 cited
Placing quantified variants of 3-SAT and Not-All-Equal 3-SAT in the polynomial hierarchy
Janosch Döcker, Britta Dorn, Simone Linz +1
The complexity of variants of 3-SAT and Not-All-Equal 3-SAT is well studied. However, in contrast, very little is known about the complexity of the problems' quantified counterpart…
cs.CC2014
Satisfying ternary permutation constraints by multiple linear orders or phylogenetic trees
Leo van Iersel, Steven Kelk, Nela Lekic +1
A ternary permutation constraint satisfaction problem (CSP) is specified by a subset Pi of the symmetric group S_3. An instance of such a problem consists of a set of variables V a…