Skip to main content
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$. ...
Huck Bennett's user avatar
  • 5,013
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 ...
a3nm's user avatar
  • 9,677
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 ...
Michael Lampis's user avatar
8 votes

What are the hardness results known for CSP over $\mathbb{F}_q$?

Here is a summary of what is known about approximability of $k$-CSP over a domain of size $q$: The best known approximation algorithms for the problem give an $\Omega(q \max(k, \log q)/q^k)$ ...
Yury's user avatar
  • 3,909
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://...
Florian's user avatar
  • 156
4 votes

Encoding quadratic constraints in a constraint satisfaction problem into SAT

This of course depends on the type of satisfaction problems you are trying you encode in SAT. Assuming the general case, where your problem falls into the class of problems that can be handled by some ...
ivcha's user avatar
  • 186
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 ...
holf's user avatar
  • 2,174
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 ...
holf's user avatar
  • 2,174
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 ...
notautogenerated's user avatar
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 ...
Emil Jeřábek's user avatar
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$-...
domotorp's user avatar
  • 14.1k

Only top scored, non community-wiki answers of a minimum length are eligible