# Tag Info

26

Yes, there has been. Moshe Vardi recently gave a survey talk at BIRS Theoretical Foundations of Applied SAT Solving workshop: Moshe Vardi, Phase transitions and computational complexity, 2014. (Moshe presents the graph of their experiment a bit after minute 14:30 in his talk linked above.) Let $\rho$ denote the clause ratio. As the value of $\rho$ ...

19

There are at least two lines of research concerning random $k\text-\mathsf{SAT}$ for formulas with a clause/variable-ratio larger than the satisfiability threshold: For such formulas lower bounds on the length of refutations in resolution and stronger propositional proof systems have been shown, starting with the paper "Many hard examples for resolution" by ...

14

Determining whether a graph $G$ has a dominating clique for: $diam(G)=1$ is trivial -- answer is always 'yes' $diam(G)=2$ is NP-complete $diam(G)=3$ is NP-complete $diam(G)\ge 4$ is trivial -- answer is always 'no' The case $diam(G)=3$ is due to Brandstädt and Kratsch, and the case $diam(G)=2$ is noted in a recent paper of mine.

11

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 strict ranking of all other vertices, admits a popular matching is in P for odd $n$ and NP-hard for even $n$. (The parameter is the vertex number $n$.) The ...

10

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 formula for the 3SAT satisfiability threshold (approximate value: 4.2667) is incorrect.

8

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 respect to some parameter $m(x)$. Then so does $L_2$, with respect to the parameter $m_2(y) := m(\varphi^{-1}(y))$. (This relies on the fact that "phase transition" ...

8

A path in an edge-colored graph is rainbow if no color appears twice on it. A graph is rainbow colored if there is a rainbow path between each pair of vertices. Let RAINBOW-$k$-COLORABILITY be the problem of deciding if a given graph can be rainbow colored using $k$ colors. For any graph $G$, the problem is easy for $k=1$ as it equals checking if $G$ is a ...

7

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-hard on graphs of diameter 2 see this paper and is again easy on graphs of diameter at least 3 see this paper.

6

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 random graph has $\Omega(n^2)$ edges, it is almost certainly Hamiltonian as $n\rightarrow \infty$, even without the constraint on the minimal degree.

4

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 widely regarded/ disseminated in the larger field (it emanates more from an empirical-oriented branch of study). its nearly an open conjecture. there is strong ...

2

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

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. uniformly in $[0,1]$), then set $w_i = x_i/X$, where $X=\sum_j x_j$. Then with high probability, almost all sets $S$ will have $\sum_{i\in S} w_i \sim 1/2$: ...

2

here is an older but relevant study/angle by a leading expert. The constrainedness knife edge Walsh 1998 he shows the parameter $\kappa$ estimates number of solutions and measures "constrainedness" and correlates/trends roughly with the clause-to-variable ratio. see p3 fig 4 in particular In figure 4, we plot the estimated constrainedness down the ...

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