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 ...
8 votes

Parameterized complexity from P to NP-hard and back again

A subset $U\subseteq V(G)$ of a graph $G$ is a disconnected cutset if $G[U]$ and $G-U$ are disconnected. Deciding if a graph of diameter 1 has a disconnected cutset is trivial. The problem becomes NP-...
  • 2,477
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 ...
4 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 ...
  • 10.9k
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.
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,258

Only top scored, non community-wiki answers of a minimum length are eligible