# Questions tagged [csp]

CSP stands for the constraint satisfaction problem.

38 questions
Filter by
Sorted by
Tagged with
1k views

• 1,723
1 vote
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, ...
• 125
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 ...
• 1,767
83 views

• 2,143
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 ...
• 11
1 vote
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 ...
• 163
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 ...
• 163
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 ...
• 41
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 ...
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 ...
• 467
1 vote
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 ...
• 29
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 ...
• 293
1 vote
82 views

• 4,258
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 ...
• 1,569
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, ...
• 2,796
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-...
• 705
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-...
• 901
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 ...
• 91
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 ...
• 436
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: ...
• 73
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 ...
• 16.7k
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 ...
• 6,001
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 ...
• 6,001
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 \$...