Questions tagged [csp]
CSP stands for the constraint satisfaction problem.
3
questions
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 ...
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 $...
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 ...