3
$\begingroup$

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.

$\endgroup$

Your Answer

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

Browse other questions tagged or ask your own question.