CSP stands for the constraint satisfaction problem.

learn more… | top users | synonyms

5
votes
2answers
113 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 ...
3
votes
1answer
179 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 ...
1
vote
0answers
67 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 ...
10
votes
1answer
183 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 ...
4
votes
1answer
149 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 ...
1
vote
1answer
2k 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 ...
6
votes
2answers
262 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 ...
3
votes
1answer
190 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 ...
26
votes
2answers
770 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, ...
2
votes
1answer
138 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 ...
12
votes
1answer
220 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 ...
8
votes
0answers
283 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 ...
22
votes
3answers
557 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 ...
5
votes
2answers
273 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: ...
17
votes
5answers
334 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 ...
16
votes
3answers
493 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 ...
8
votes
1answer
196 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 ...
12
votes
1answer
277 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 ...
9
votes
3answers
402 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 ...