New answers tagged np-complete
14
One example: choosing the property "G contains a node that has an edge to all nodes in G" makes P1 trivial in $O(n + m)$ (pick node with largest degree), but makes P2 the problem of finding the minimum size dominating set, which is NP-hard.
0
Try to think of some game's algorithms or processes you could easily verify on correctness given all the answers and steps towards the correct solution. Thus we can conclude that we can verify a correct solution in polynomial time in comparison to creating the solution to the problem yourself.
Now try the reverse order, construct some solution for solving ...
2
You can trivially consider NEXP-complete problems and they satisfy all 3 conditions that you're looking for. And by the Time Hierarchy Theorem, NP is strictly in NEXP.
4
Solving Parity games has recently been shown to be in QP:
https://www.comp.nus.edu.sg/~sanjay/paritygame.pdf
Parity games arise naturally in many formal verification contexts, such as LTL synthesis and $\mu$-calculus satisfiabiability.
Parity games were known to be in $NP\cap coNP$, and even in $UP\cap coUP$. In addition, there have been repeated ...
2
In Classical algorithms, correlation decay, and complex zeros of partition functions of quantum many-body systems by Aram Harrow, Saeed Mehraban, and Mehdi Soleimanifar
a quasi-polynomial time classical algorithm that estimates the partition function of quantum many-body systems at temperatures above the thermal phase transition point
is presented.
Not ...
3
Under Karp reductions, the answer is exactly $\mathbf{NP}$: it is not hard to see that if a language is Karp-reducible to any $\mathbf{NP}$-language, then it is in $\mathbf{NP}$ too. On the other hand, all of $\mathbf{NP}$ reduces to $\mathbf{NP}$-complete languages by definition.
Under Turing reductions, the answer is the class $\mathbf{P}^\mathbf{NP}$: ...
Top 50 recent answers are included
