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.

Improve this question
$\endgroup$

2 Answers 2

Reset to default
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).

Improve this answer
$\endgroup$
1
  • $\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
    Commented Jul 3, 2012 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.

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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