# NP-complete variants of NPI problems

Motivated by these posts, An NP-complete variant of factoring and Relationship between symmetry and computational intractability, It seems to be worthwhile to investigate the different factors that increase the hardness of problems in $NPI$ from an intermediate complexity to full $NP$-completeness. I'm interested in other $NP$-complete variants of $NPI$ problems. Ideally, a recent survey paper of $NP$-complete variants of $NPI$ problems would be the best answer?

EDIT July 1st, 2012 The bounty will be awarded to the person that lists the maximum number of such problems.

From Papadimitriou's paper "On total functions, existence, theorems and computational complexity":

Nondeterministic multivalued functions with values that are polynomially verifiable and guranteed to exist form an interesting class (called $TFNP$) between P and NP ...

.... It is quite interesting, in view of Theorem 2.1, that in some cases of problems in $TFNP$, if together with the input we are also given one of the solutions that are guaranteed to exist, then the problem indeed becomes NP-complete ...

For example the TRICHROMATIC TRIANGLE problem is in $TFNP$, but the SECOND TRICHROMATIC TRIANGLE is $NPC$ (the paper contains a sketch of the proof).

• TRICHROMATIC TRIANGLE was later shown to be PPAD-complete, which is a well-known class by now, while imo similar to SECOND TRICHROMATIC TRIANGLE one can make an NPC variant of basically any TFNP problem, so this kind of examples I would call cheating. Jul 3, 2012 at 18:29

The graph isomorphism problem is in NP but not known to be in P or NP-complete.

A generalization, the subgraph isomorphism problem, is NP-complete since asking if some subgraph of the input graph with $n$ vertices is isomorphic to a cycle of length $n$ is the Hamiltonian cycle problem.

• Thanks Tyson. I'm aware of these trivial examples. I'm only interested in non-trivial cases. Jul 1, 2012 at 19:09
• What does it mean to be a trivial example? Jul 1, 2012 at 21:20
• I suspect "trivial" is being used as a synonym for "known to the OP" Jul 2, 2012 at 3:50
• @Tyson, in addition to Suresh's comment, "non-Trivial" means "interesting" examples to the experts in TCS. For instance, I would consider the examples which I cited in my question as "interesting". I hope this would help. Jul 2, 2012 at 8:20