Are weakly polynomial time algorithms truly polynomial?

Question

I've been looking through a ton of sources to try and understand the definitions of strongly and weakly polynomial time algorithms. Wikipedia states an algorithm runs in strongly polynomial time if

1. the number of operations in the arithmetic model of computation is bounded by a polynomial in the number of integers in the input instance; and
2. the space used by the algorithm is bounded by a polynomial in the size of the input.

A weakly polynomial time algorithm is then just an "algorithm that runs in polynomial time but that is not strongly polynomial."

What I'm confused about is how weakly polynomial time algorithms can actually be said to be polynomial. As stated in this post in reference to weakly polynomial time algorithms,

The algorithm is already polynomial time in the arithmetic model, so as long as its space is bounded in the TM model then the rest of the algorithm is still polynomial time in the TM model. Think of it like this, when converting from the arithmetic model to the TM model, the only thing that can go wrong is the space. The numbers you produce need to be representable in a number of bits that is polynomial in the number of bits in the input. So long as that holds, the rest of the algorithm is still polynomial time in the TM model.

I understand the difference between the arithmetic model and the TM model. But this quote and the wikipedia definition itself seem to imply that a weakly polynomial time algorithm will not run in polynomial time on a TM. This being because (to my understanding) if the space being used isn't bound by a polynomial in the size of the input, just the time spent allocating the space necessary to run the algorithm on a TM eliminates any hope of polynomial time. The classic example is in the post I linked above and the Wikipedia article and involves calculating $2^{2^n}$ given $2^n$.

So how can we say weakly polynomial algorithms are still polynomial? There seems to be a consensus that weakly polynomial is better than pseudo-polynomial, but aren't they both not polynomial on a TM?

Edit: I would also like to add that confusingly this post states that

Consider running either one on a Turing Machine. Both will run in a number of steps polynomial in the length of binary-encoded input.

This seems to contradict the previous post I linked which states

Any strongly-polynomial time algorithm can be converted into a polynomial time algorithm on a TM by replacing the arithmetic operations with equivalent algorithms in the TM model.

suggesting that the difference is weakly polynomial time algorithms don't run in polynomial time on a TM. Either I'm missing something fundamental or multiple definitions seem to be floating around.

Answer 1

As Wikipedia says, there are two conditions for strongly polynomial time algorithms:

1. the number of operations in the arithmetic model of computation is bounded by a polynomial in the number of integers in the input instance; and
2. the space used by the algorithm is bounded by a polynomial in the size of the input.

I will simply call these two conditions as condition 1 and condition 2 in this answer.

---

The algorithm is already polynomial time in the arithmetic model, so as long as its space is bounded in the TM model then the rest of the algorithm is still polynomial time in the TM model. Think of it like this, when converting from the arithmetic model to the TM model, the only thing that can go wrong is the space. The numbers you produce need to be representable in a number of bits that is polynomial in the number of bits in the input. So long as that holds, the rest of the algorithm is still polynomial time in the TM model.

This paragraphs is describing why condition 2 is necessary for strongly polynomial time algorithm, it is not stating the difference between strongly and weakly polynomial time algorithms. In fact, condition 2 is also necessary for weakly polynomial time algorithm, and the example algorithm that computes $2^{2^n}$ given $2^n$ is NOT weakly polynomial (and is even not a polynomial time algorithm).

In fact, it is condition 1 that describes the difference between strongly and weakly polynomial time algorithms. Note the definition of strongly polynomial time algorithms is equivalent to

• condition 1; and
• the algorithm is a polynomial time algorithm (in the TM model)

While the definition of weakly polynomial time algorithms is equivalent to

• condition 1 is not satisfied; and
• the algorithm is a polynomial time algorithm (in the TM model)

It is more clear to see the difference between strongly and weakly polynomial time algorithms with these two redefinitions.

---

This post is wrong to suggest the difference is weakly polynomial time algorithms don't run in polynomial time on a TM. I have added a comment on that post addressing this issue.