MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

Partition problem is weakly NP-complete since it has polynomial (pseudo-polynomial) time algorithm if input integers are bounded by some polynomial. However, 3-Partition problem is strongly NP-complete problem (even if input integers are bounded by a polynomial).

Assuming, $\mathsf{P \ne NP}$, Can we prove that intermediate NP-complete problems must exist? If the answer is yes, Is there such "natural" candidate problem?

Here, Intermediate NP-complete problem is an NP-complete problem that neither has a pseudo-polynomial time algorithm nor NP-complete in the strong sense.

I guess that there is an infinite hierarchy of intermediate NP-complete problems between weak NP-completeness and strong NP-completeness.

An alternative way to pose the question is:

Assuming, $\mathsf{P \ne NP}$, Can we prove the existence of NP-complete problems that neither have polynomial time algorithm nor NP-complete when the numerical inputs are presented in unary? If the answer is yes, Is there such "natural" candidate problem?

The reverse direction of the implication is true. The existence of such "intermediate" $NP$-complete problems implies $\mathsf{P \ne NP}$ because if $\mathsf{ P=NP}$ then unary $NP$-complete problems are in $P$.

This was posted on CSTheory StackExchange.

share|cite|improve this question

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.