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 ...
user avatar
  • 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 ...
user avatar
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 ...
user avatar
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-...
user avatar
  • 2,477
6 votes

What's the probability for a random graph with degrees greater than 1 to be Hamiltonian?

The probability that a random graph with $n$ nodes and $cn\log n$ edges contains a Hamiltonian circuit tends to $1$ as $n\rightarrow\infty$ (and for sufficiently large $c$) (Pósa 1976). Since an ER ...
user avatar
  • 1,448
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 ...
user avatar
  • 10.8k
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.
user avatar
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. ...
user avatar
  • 8,273

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