Hot answers tagged


A general list of NP-complete problems can be found in Garey & Johnson's book "Computers and Intractability". It contains an appendix that lists roughly 300 NP-complete problems, and despite its age is often suggested when one wants a list of NP-complete problems. I haven't read the book, but based on its reputation it would be a quite good start to any ...


You may also have a look at the Compendium of Parameterized Problems by Marco Cesati ( which contains a list of many hard graph problems. The compendium deals with the parameterized complexity of these problems for various parameterizations and the list of results is partially outdated by now but since ...


I believe everything you said is correct. I note that your point #3 could hold regardless of points #1 and #2 - points #1 and #2 are just a concrete example of where this has provably happened.


There are still issues with the formatting, so here's an attempt to re-interpret your problem. Given A collection $\mathcal{C} = \{C_1, C_2, C_3, \cdots, C_m\}$ of sets of points from some universe $U$. A similarity function $w: (U \times U) \rightarrow \mathbb{R}_0^+$ (or some similar codomain). Presumably this function is symmetric and nonnegative. Find ...


A propositional proof system in which all tautologies have a "short" proof is called a super-propositional-proof system. Such a system exists iff NP = CoNP. If NP != CoNP then P != NP. So, it's not necessarily the only way to prove P != NP, but you could do so by proving a super-propositional-proof system cannot exist.

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