Questions tagged [csp]

CSP stands for the constraint satisfaction problem.

Filter by
Sorted by
Tagged with
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
12 votes
3 answers
537 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
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