4
$\begingroup$

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.

$\endgroup$
5
+100
$\begingroup$

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

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – domotorp Jul 3 '12 at 18:29
1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Thanks Tyson. I'm aware of these trivial examples. I'm only interested in non-trivial cases. $\endgroup$ – Mohammad Al-Turkistany Jul 1 '12 at 19:09
  • 6
    $\begingroup$ What does it mean to be a trivial example? $\endgroup$ – Tyson Williams Jul 1 '12 at 21:20
  • 2
    $\begingroup$ I suspect "trivial" is being used as a synonym for "known to the OP" $\endgroup$ – Suresh Venkat Jul 2 '12 at 3:50
  • $\begingroup$ @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. $\endgroup$ – Mohammad Al-Turkistany Jul 2 '12 at 8:20

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.