NP-complete variants of NPI problems

Question

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.

score 5 · Accepted Answer · answered Jul 01 '12 at 23:25

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. — domotorp, Jul 03 '12 at 18:29

score 1 · Answer 2 · answered Jul 01 '12 at 17:22

1

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.

answered Jul 01 '12 at 17:22

Tyson Williams

4,258
2
23
44

Thanks Tyson. I'm aware of these trivial examples. I'm only interested in non-trivial cases. – Mohammad Al-Turkistany Jul 01 '12 at 19:09
6

What does it mean to be a trivial example? – Tyson Williams Jul 01 '12 at 21:20
2

I suspect "trivial" is being used as a synonym for "known to the OP" – Suresh Venkat Jul 02 '12 at 03: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. – Mohammad Al-Turkistany Jul 02 '12 at 08:20

NP-complete variants of NPI problems

2 Answers2