# Tag Info

### 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
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,781
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 ...
• 35.8k

### 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

### 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 ...
• 1,448
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.8k
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. ...