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.


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


Refolding an unfolded origami is NP-hard.


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

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