Questions tagged [csp]

CSP stands for the constraint satisfaction problem.

Filter by
Sorted by
Tagged with
17 votes
2 answers
1k views

Is there a SETH (Strong Exponential Time Hypothesis) for CSP (Constraint Satisfaction Problem)?

The Constraint Satisfaction Problem I mentioned is similar to CNF-SAT: A variable can take values from some finite domain $D$ where $|D| = d$. A literal of variable $x$ is an expression of the form $x\...
Junqiang Peng's user avatar
4 votes
1 answer
91 views

Methods for Determining the minimal Width of Resolution Refutations for CNF Formulas

Recall that the width of a resolution refutation $R$ of a CNF formula $F$ is the maximal number of literals in any clause occurring in $R$. I am intersting in finding the minimal width of some certain ...
Jxb's user avatar
  • 316
13 votes
1 answer
252 views

Complexity of 1-or-3-in-3-SAT (odd-3-SAT)

Consider a 3-CNF formula $\Phi$, i.e., a conjunction of clauses of 3 literals. I call odd-SAT (or 1-or-3-in-3-SAT) the problem of checking whether there is an assignment of the variables such that ...
a3nm's user avatar
  • 9,232
1 vote
0 answers
21 views

Optimization: Turning a sparse graph of probabilities into the maximum likelihood DAG

I have a sparse matrix of probabilities that I want to turn into a DAG. If x[m,n] = pr it means that m is a descendent (direct or transitively) of n with probability pr. I want to construct a DAG over ...
Joseph Turian's user avatar
0 votes
0 answers
83 views

Does NP-completeness in one graph class imply not NP-intermediate in another graph class?

I am trying to wrap my head around implications of CSP dichotomy theroem. CSP is short for Constraint Satisfaction Problem. The following seem to be known results (I shall focus on decision problems ...
Cyriac Antony's user avatar
2 votes
0 answers
68 views

Is k-ACYCLIC COLOURABLITY in CSP?

All graphs in this question are finite, simple and undirected. Let $k$ be a fixed positive integer. A $k$-colouring of a graph $G$ is a function $f\colon V(G)\to\{1,2,\dots,k\}$ such that $f(u)\neq f(...
Cyriac Antony's user avatar
1 vote
1 answer
119 views

On motivation towards study of width parameters beyond treewidth

Many width parameters are invented to capture the tractability of CSP (and its equivalent problem, conjunctive queries (CQ) evaluation): treewidth, hypertree width, generalized hypertree width, ...
xxks-kkk's user avatar
  • 125
3 votes
1 answer
192 views

When is hypertree width more useful than generalized hypertree width?

In analysis of CSPs, there are three width notions that are analogous to treewidth: hypertree width (hw), generalized hypertree width (ghw) and fractional hypertree width (fhw). Moreover the ...
Laakeri's user avatar
  • 1,767
6 votes
1 answer
83 views

NP-intermediate approximation regimes for natural problems within the MAX-k-CSP family

I would like to know whether there are any examples of natural problems within the MAX-$k$-CSP family for which (under standard/reasonable conjectures) we believe the following: There is a value $\...
Abel Molina's user avatar
  • 1,424
8 votes
1 answer
462 views

complexity of a constraint satisfaction promise problem

(This is the "upper end" of my question from over 10 months ago on cs.stackexchange. That question and the "lower end" I asked here over 8 months ago, which I also have a bounty ...
user avatar
7 votes
1 answer
221 views

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

I found two related papers, There is a UGC hardness result here, https://www.cs.cmu.edu/~venkatg/pubs/papers/qaryCSP.pdf A kind of a stronger result might be found in these two other papers, http://...
gradstudent's user avatar
  • 1,443
5 votes
1 answer
294 views

Does every NO instance of this promise problem have a local refutation?

For the following equivalent questions, you choose whether-or-not the 3 variables in a clause must be distinct. Is there an integer $k$ such that for all 3-SAT formulas $\mathcal{F}$ without ...
user avatar
10 votes
2 answers
363 views

Complexity of digraph homomorphism to an oriented cycle

Given a fixed directed graph (digraph) $D$, the $D$-COLORING decision problem asks whether an input digraph $G$ has a homomorphism to $D$. (A homomorphism of $G$ to $D$ is a mapping $f$ of $V(G)$ to $...
Florent Foucaud's user avatar
0 votes
0 answers
140 views

CSP-problem, based on context-free grammar

I'm trying to solve a CSP (Constraint-Satisfaction-Problem), which is based on arbitrary context-free grammars. A quick example: Let's say we have a context-free grammar with the following production ...
Rob's user avatar
  • 11
1 vote
1 answer
142 views

Confusion in 2012 paper by Austrin and Håstad regarding hardness of approximating GLST

The paper in question is "On the Usefulness of Predicates", Per Austrin, Johan Håstad (arXiv:1204.5662 [cs.CC]). On page 13, Example 8.2 they define a predicate $P$ which is $GLST$ with an ...
Mark's user avatar
  • 163
4 votes
1 answer
88 views

Definition of Projection Measure in the characterization of strong approximation Resistance in a paper by Khot et al

I'm reading a paper about Constraint Satisfaction Problems, specifically "A Characterization of Strong Approximation Resistance", Subhash Khot, Madhur Tulsiani, Pratik Worah (ECCC TR13-075). The ...
Mark's user avatar
  • 163
4 votes
1 answer
168 views

How to estimate the probability of distribution of a variable in a Constraint Satisfication Problem

Consider that we have a state space of n random variables, for simplicity, the variable value can be 0 or 1. Each variable has its probability distribution when it is not constrained, also for ...
Wen's user avatar
  • 41
6 votes
0 answers
127 views

General Results for Complicated Constraint Satisfaction Problem

Consider the following problem: on a finite two-dimensional grid (say the grid points are vertices of a graph), I need to color the vertices in such a way to satisfy the existence and nonexistence of ...
user17356's user avatar
5 votes
2 answers
424 views

Learnability of constraint satisfaction problems CSPs?

This may sound more like a soft question but I am struggling to find an answer for it. While the learnability of Bayesian Networks and other graphical models are well detailed in the literature of ...
seteropere's user avatar
1 vote
1 answer
186 views

Encoding quadratic constraints in a constraint satisfaction problem into SAT

It seems like most constraint satisfaction problems can be posed in terms of SAT. The question is two fold: How can any CSP with quadratic constraints be framed as a satisfiability instance Is ...
quadcons's user avatar
4 votes
1 answer
259 views

How is this graphical representation of SAT/CSP instances called?

Given a CNF formula (SAT problem), we can construct the constraint/dependency graph, which contains a vertex for each variable and a hyperedge for each clause. Same goes for CSPs, where we have a ...
ziggystar's user avatar
  • 293
1 vote
0 answers
82 views

Constraint problem

I have encountered a constraint problem and I would like to know if there exists a name and implemented solvers for this type of constraint problem. My constraints are of the forms. 1) $CONSTANT \in ...
Evgenii.Balai's user avatar
13 votes
1 answer
328 views

Schaefer's theorem and CSPs of unbounded width

Schaefer's dichotomy theorem shows that each CSP problem over $\{0,1\}$ is either solvable in polynomial time or is NP-complete. This applies only for CSP problems of bounded width, excluding SAT and ...
Yuval Filmus's user avatar
  • 14.4k
4 votes
1 answer
215 views

Constraint satisfaction problem on a graph

Consider the set $S = \{1, \dots, n\}$ and $n$ subsets $S_i \subseteq S$ of size $d$ each (think of $S_i$ as neighborhoods of vertex $i$ in some $d$-regular graph, although the graph structure is not ...
Marcin Kotowski's user avatar
12 votes
2 answers
12k views

Is the N Queens problem NP-hard?

The N-queen problem is this: Input : N Output : A placement of N "queens" on an NXN chessboard such that no two queens lie on the same row, column or diagonal. Doing a google search on this, I ...
Anshul Singhle's user avatar
7 votes
2 answers
356 views

What is known about the H-factor problem?

Background The $\mathcal{H}$-factor problem (a.k.a. the degree prescribed factor problem, or the degree prescribed subgraph problem) is defined as follows: Given a graph $G=(V,E)$ and a set $H_v \...
Tyson Williams's user avatar
3 votes
1 answer
330 views

A variant of betweenness problem

Is there any non-trivial approximation algorithm for a variant of betweenness problem: namely, we want to minimize the number of unsatisfied triples rather than to maximize the number of satisfied ...
ilyaraz's user avatar
  • 1,569
28 votes
2 answers
2k views

Ladner's Theorem vs. Schaefer's Theorem

While reading the article "Is it Time to Declare Victory in Counting Complexity?" over at the "Godel's Lost Letter and P=NP" blog, they mentioned the dichotomy for CSP's. After some link following, ...
user834's user avatar
  • 2,796
2 votes
1 answer
207 views

hardness of approximation result for a Min-CSP, by reduction from PCPs

Reduction from PCPs allow us to prove hardness of approximation results for a number of constraint satisfaction problems. I've seen such a reductions only for Max-CSPs. Is this possible only for Max-...
j.s.'s user avatar
  • 705
12 votes
1 answer
307 views

Any results on binary boolean CSP beyond the fixed-parameter tractability of almost 2SAT problem?

Let $\varphi$ be a 2CNF formula and $k$ a nonnegative integer. It is proved in this paper that the problem of deciding whether one can delete at most $k$ clauses to make $\varphi$ satisfable, is fixed-...
Regularity's user avatar
9 votes
0 answers
505 views

When is CSP faster than SMT/SAT?

Do CSP solvers have any fundamental advantages over SMT/SAT solvers, in terms of performance? The answer is going to be problem dependent, so I should also ask: what does a problem need to contain in ...
jah's user avatar
  • 91
22 votes
3 answers
622 views

Educational Source or Survey on Analysis of Semidefinite Program?

When designing approximation algorithms one sometimes solves a semidefinite program followed by a rounding step. An often used example to illustrate this is Max-Cut. (See e.g. Approximation Algorithms ...
Michael's user avatar
  • 436
7 votes
2 answers
489 views

What relation is between constraint satisfaction problems and constraint programming?

Are programs written in the constraint programming (CP) paradigm more expressive than problems defined as constraint satisfaction problem (CSP)? Wikipedia says about Constraint_programming: ...
Scrool's user avatar
  • 73
17 votes
5 answers
411 views

Open or Interactive Constraint Satisfaction

In the past, I implemented coordination models using SAT and regular constraint satisfaction as the core workhorse in their engines. Continuing in this line of work, I would like to make the models ...
Dave Clarke's user avatar
  • 16.7k
16 votes
3 answers
569 views

UGC hardness of the predicate $NAE(x_1, ..., x_\ell)$ for $x_i \in GF(k)$?

Background: In Subhash Khot's original UGC paper (PDF), he proves the UG-hardness of deciding whether a given CSP instance with constraints all of the form Not-all-equal(a, b, c) over a ternary ...
Daniel Apon's user avatar
  • 6,001
10 votes
1 answer
326 views

CSPs with unbounded fractional hypertree width

At SODA 2006, Martin Grohe and D$\acute{\rm a}$niel Marx's paper "Constraint solving via fractional edge covers" (ACM citation) showed that for the class of hypergraphs $H$ with bounded fractional ...
Daniel Apon's user avatar
  • 6,001
12 votes
1 answer
326 views

Finding the penumbra of a Constraint Satisfaction Problem

The following question has come up a number of times when testing the security of a system or model. Motivation: Software security flaws often come not from bugs due to valid inputs, but bugs ...
Dave Clarke's user avatar
  • 16.7k
12 votes
3 answers
534 views

Hard gaps in maximum constraint satisfaction problems?

An equivalent formulation of PCP theorem is: For Max 3-SAT it is $NP$-hard to distinguish between satisfiable formulas and formulas where at most $r$-fraction of the clauses are satisfiable (for some $...
Mohammad Al-Turkistany's user avatar