1
$\begingroup$

Consider the computational problems in which the input is a set of $n$ integers with maximum magnitude $M$. According to Erik Demaine's lecture notes, assuming $P\neq NP$, the following are true:

  • If a problem is strongly NP-hard, then it does not have a pseodupolynomial time algorithm (an algorithm with run-time $\text{poly}(n,M)$).
  • If a problem is weakly NP-hard, then it does not have a weakly polynomial time algorithm (an algorithm with run-time $\text{poly}(n,\log{M})$), but it may have a pseudopolynomial time algorithm.

Is there a hardness concept X such that, if a problem is "X hard", then it does not have a strongly polynomial time algorithm (an algorithm with run-time $\text{poly}(n)$), but it may have a weakly-polynomial time algorithm?

A related question: is there a natural problem for which it is proved that no strongly-polynomial-time algorithm exists (unless P=NP)?

$\endgroup$
3
  • 3
    $\begingroup$ Erik Demaine is being rather informal, or conversely, is working within the framework of computational geometry. There is only one notion of NP-hardness. "Weak NP-hardness" refers to NP-hardness when numbers are encoded in binary. "Strong NP-hardness" refers to NP-hardness when numbers are encoded in unary. $\endgroup$ – Yuval Filmus Jun 11 at 14:02
  • 1
    $\begingroup$ @YuvalFilmus I partially agree with you. However, if we only consider the numbers encoded in binary then a "weak NP-hard" problem has a singly exponential algorithm in the input size, i.e., $2^{\log M}$, and a "strong NP-hard" does not have a singly exponential algorithm but some higher exponential algorithm is possible like $2^{2^{\log M}}$. Isn't there some complexity class for such distinction? $\endgroup$ – Inuyasha Yagami Jun 11 at 16:10
  • 1
    $\begingroup$ Standard complexity theory is only interested in a single parameter, namely the size of the input. Parameterized complexity also cares about other parameters, so perhaps that's the proper place to look. $\endgroup$ – Yuval Filmus Jun 11 at 16:12

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.