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