# What computational hardness concept corresponds to strongly-polynomial time algorithms?

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)?

• 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. Jun 11 '21 at 14:02
• @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? Jun 11 '21 at 16:10
• 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. Jun 11 '21 at 16:12