<p>From Papadimitriou's paper "<a href="http://theory.stanford.edu/~megiddo/pdf/papadimX.pdf" rel="noreferrer">On total functions, existence, theorems and computational complexity</a>":</p>

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

<p><em>.... 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 ...</em></p>

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

CC BY-SA 3.0
2012-07-03T18:29:52.070Z
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
CC BY-SA 3.0
2012-07-01T23:25:12.123Z
2012-07-01T23:25:12.123Z
Marzio De Biasi
<p>The <a href="http://en.wikipedia.org/wiki/Graph_isomorphism_problem" rel="nofollow">graph isomorphism problem</a> is in NP but not known to be in P or NP-complete.</p>

<p>A generalization, the <a href="http://en.wikipedia.org/wiki/Subgraph_isomorphism_problem" rel="nofollow">subgraph isomorphism problem</a>, 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 <a href="http://en.wikipedia.org/wiki/Hamiltonian_cycle" rel="nofollow">Hamiltonian cycle problem</a>.</p>

CC BY-SA 3.0
2012-07-01T19:09:20.530Z
Thanks Tyson. I'm aware of these trivial examples. I'm only interested in non-trivial cases.
Mohammad Al-Turkistany
CC BY-SA 3.0
2012-07-01T21:20:09.830Z
What does it mean to be a trivial example?
Tyson Williams
CC BY-SA 3.0
2012-07-02T03:50:03.290Z
I suspect "trivial" is being used as a synonym for "known to the OP"
Suresh Venkat
CC BY-SA 3.0
2012-07-02T08:20:19.047Z
@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
CC BY-SA 3.0
2012-07-01T17:22:51.043Z
2012-07-01T17:22:51.043Z
Tyson Williams
<p>Motivated by these posts, <a href="https://cstheory.stackexchange.com/q/4769/495">An NP-complete variant of factoring</a> and <a href="https://cstheory.stackexchange.com/q/871/495">Relationship between symmetry and computational intractability</a>, 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?</p>

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

<cc.complexity-theory><np-hardness>
NP-complete variants of NPI problems
Mohammad Al-Turkistany
# NP-complete variants of NPI problems

(Asked by: username_0 on 2011-05-27)

Motivated by these posts, [An NP-complete variant of factoring](https://cstheory.stackexchange.com/q/4769/495) and [Relationship between symmetry and computational intractability](https://cstheory.stackexchange.com/q/871/495), 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.

**Tags:** cc.complexity-theory, np-hardness


---

## 2 answers

### Answer by username_1 on 2012-07-01. Score: 5 | Accepted answer

From Papadimitriou's paper "[On total functions, existence, theorems and computational complexity](http://theory.stanford.edu/~megiddo/pdf/papadimX.pdf)":

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

> **Comments:**
> **username_2**: 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.  

---

### Answer by username_3 on 2012-07-01. Score: 1

The [graph isomorphism problem](http://en.wikipedia.org/wiki/Graph_isomorphism_problem) is in NP but not known to be in P or NP-complete.

A generalization, the [subgraph isomorphism problem](http://en.wikipedia.org/wiki/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](http://en.wikipedia.org/wiki/Hamiltonian_cycle).

> **Comments:**
> **username_0**: Thanks Tyson. I'm aware of these trivial examples. I'm only interested in non-trivial cases.  
> **username_3**: What does it mean to be a trivial example?  
> **username_4**: I suspect "trivial" is being used as a synonym for "known to the OP"  
> **username_0**: @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.  

---

