11
votes
Parameterized complexity from P to NP-hard and back again
This is an interesting (and surprising) example for a P $\to$ NP-hard $\to$ P $\to$ NP-hard $\to \cdots$ phase transition:
Deciding if a complete graph on $n$ vertices, in which each vertex has a ...
- 2,477
10
votes
Accepted
Random 3-SAT: What is the consensus experimental range of the threshold?
In light of the Ding--Sly--Sun verification of the 1-step Replica Symmetry Breaking picture for kSAT (when k is large enough) I think experts would now be pretty surprised if the MPZ/MMZ-conjectured ...
- 1,801
8
votes
Accepted
Does p-isomorphism preserve phase transition?
Yes, but I'm not sure it means much. Yes in a trivial way: suppose $\varphi$ is an isomorphism between two $\mathsf{NP}$-complete languages $L_1, L_2$, and $L_1$ exhibits a phase transition with ...
- 36.9k
5
votes
Accepted
How common is phase transition in NP-complete problems?
expert researchers in this area basically assert that phase transitions are a universal feature of NP complete problems although this has yet to be formulated/ proven rigorously and it is not yet ...
- 11k
2
votes
Generating hard satisfiability problems with given constraint graph
It sounds like what you want are universal factor graphs. Such graphs exist for every NP-hard boolean CSP and in many cases are optimally inapproximable.
- 513
2
votes
Phase transition in counting feasible solutions to knapsack problems?
I don't have a reference for you, just a minor remark that is too large for a comment.
We assume $w$ is chosen as follows. Choose r.v. $x\in[0,1]^n$ uniformly at random (i.e., each $x_i$ is i.i.d. ...
- 9,595
Only top scored, non community-wiki answers of a minimum length are eligible