15
votes
Accepted
Is there a SETH (Strong Exponential Time Hypothesis) for CSP (Constraint Satisfaction Problem)?
This CSP is known to be SETH-hard. More precisely, assuming SETH, for any constant $\varepsilon > 0$ there is no $d^{(1-\varepsilon)n}$-time algorithm for solving this CSP with domain size $d$.
...
- 5,143
14
votes
Accepted
Complexity of 1-or-3-in-3-SAT (odd-3-SAT)
Somewhat surprisingly to me, this problem is in fact in PTIME.
The key insight is that, considering a clause $C$, letting $0 \leq k \leq 3$ be the number of negated literals in $C$, then the clause is ...
- 9,838
8
votes
Is there a SETH (Strong Exponential Time Hypothesis) for CSP (Constraint Satisfaction Problem)?
To give an alternative (slightly older) reference to the one proposed in another answer, the result "If the SETH is true, then $n$-variable CSP over alphabets of size $d$ cannot be solved in time ...
- 3,722
4
votes
Accepted
Complexity of digraph homomorphism to an oriented cycle
There recently has been some activity in this area. We wrote a program to determine the smallest NP-complete oriented trees, the smallest ones have 20 vertices. More details can be found here https://...
- 156
4
votes
Accepted
When is hypertree width more useful than generalized hypertree width?
Every XP/FPT algorithm parametrized by htw also gives an XP/FPT algorithm parametrized by ghtw (provided that the decomposition is given in the input) since there is a linear relation between ghw and ...
- 2,344
3
votes
On motivation towards study of width parameters beyond treewidth
It is not hard to see that if a class of queries has arity bounded by $a$ and hypertree width bouded by $k$, then it will also have treewidth bounded by $a\cdot k$. Indeed, any bag in a hypertree ...
- 2,344
2
votes
Methods for Determining the minimal Width of Resolution Refutations for CNF Formulas
Partially answering question (2), the Prover-Delayer game of Atserias and Dalmau can be interpreted as a more general "dag-like query complexity" specialized to CNFs. See e.g. GGKS'18. And ...
- 216
2
votes
NP-intermediate approximation regimes for natural problems within the MAX-k-CSP family
The sidebar algorithm has done its work, and linked to this similar question. The accepted answer there explains that under the Unique Games Conjecture, no such regimes exist.
2
votes
complexity of a constraint satisfaction promise problem
Concerning the question whether Shaefer’s dichotomy theorem (or more generally, the Feder–Vardi conjecture, recently proved by Bulatov and Zhuk) can be generalized to promise problems: the complexity ...
- 18.6k
2
votes
Accepted
Does every NO instance of this promise problem have a local refutation?
So if I understood well, your problem in the language of graph theory would be as follows:
Is there a $k$ such that if for a $3$-uniform hypergraph for any $k$ of its edges we can select a $1$-...
- 14.2k
Only top scored, non community-wiki answers of a minimum length are eligible