New answers tagged np-hardness
4
As proved in this paper:
http://www.cs.technion.ac.il/users/wwwb/cgi-bin/tr-get.cgi/1991/CS/CS0699.revised.pdf
If P != NP can be shown to be independent
of Peano Arithmetic, then NP has extremely-close-to-polynomial deterministic time upper bounds. In particular, in such a case, there is a DTIME(n^1og*(n)) algorithm
that computes SAT correctly on ...
16
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.
2
EDIT: changed a few things to make this work with the new constraint, also rewrote the whole proof to add details and clarity.
The following is a reduction of minimum vertex cover to your problem.
Take the graph $(V, E)$ we want to solve minimum vertex cover on. Set $|V_{1}| = |V|^{2} + |V| + |E|$, $|V_{2}| = |E| + |V|$.
To every node $x \in V$ there ...
Top 50 recent answers are included
