Efficient comparison, using only sum, product, difference, and conditional jump if zero

I was wondering how small we could make the instruction set of a typical machine that supports a single datatype: arbitrary integers. If you need a heap, you declare an integer variable $$h$$ where you can individually (hopefully) address bits.

So was wondering, in addition to $$+, -, \cdot$$ (no $$\%$$) what else is needed to implement $$\gt$$ efficiently? Let's say we have a single kind of conditional branch statement:

$$\text{goto_line } l \text { if } a = 0$$

Then can we implement $$\gt$$ efficiently? By efficiently I mean that an algorithm runs in worst case, polynomial-time, if and only if there exists a program implementing the algorithm on the above machine that runs in polynomial-time (roughly speaking).

• The comparison $x>0$ can be evaluated in exponential time by a simple loop that increments/decrements $x$ until the value reaches zero, but I'm not sure how to do it in polynomial time. Without goto, you can't do it, at any running time: any straight-line program that uses only $+$, $-$, $\cdot$ can be expressed as a polynomial of finite degree, and there is no finite-degree polynomial so that $p(x)=0$ for $x>0$ and $p(x)\ne 0$ for $x\le 0$.
– D.W.
Jan 17, 2022 at 15:23
• Here was my failed attempt to construct a lower bound: Consider any finite path through the code (i.e., choosing for each goto whether it is taken or not). Then the values $x$ that cause the code to take that path are the set $$S=\{x \mid p_1(x)=0,\dots,p_m(x)=0,q_1(x)\ne 0,\dots,q_n(x)=0\}.$$ Set $P(x)=p_1(x)^2+\dots + p_m(x)^2$ and $Q(x)=q_1(x) \cdots q_n(x)$ so that $S=\{x \mid P(x)=0,Q(x) \ne 0\}$. Then $S$ is either a finite set or co-finite set. If finite, $|S| \le \sum_i \deg p_i(x)$; if co-finite $|\overline{S}| \le \sum_i \deg q_i(x)$. That doesn't seem to go anywhere, though.
– D.W.
Jan 17, 2022 at 15:30
• Overall, I doubt it can be done in polynomial time with those operators, though I can't prove it.
– D.W.
Jan 17, 2022 at 15:36

Any such algorithm requires exponential time. Here is a proof sketch (omitting technicalities).

Let $$n$$ be the input length. The input is $$-2^n \lt x \lt 2^n$$ and the algorithm determines $$x \gt 0$$. An algorithm for the problem can be represented as an infinite decision tree, where each node is either a leaf (termination) or a branch with "zero" and "nonzero" child nodes.

The operand of each branch node can be represented as a polynomial of $$x$$. Without loss of generality, I assume every such polynomial is non-constant.

Consider the path from the root where "nonzero" branch is taken at every branch. Let $$p_i$$ be the $$i$$'th polynomial. Then, because a non-constant polynomial of degree $$d$$ can have at most $$d$$ roots, at least $$2^{n+1} - \sum_{i=1}^{t-1} \mathrm{deg}(p_i) - O(1)$$ inputs from $$(-2^n,2^n)$$ will take this nonzero-only path. The degree of the polynomial isn't be too large because it could have taken at least $$\deg(p_i)$$ time to compute this value. Thus, the algorithm takes an exponential time to terminate.

• This proof doesn't look correct to me. Consider the following program: "x := x*x; x := x*x; x := x*x; ..." After $k$ steps, you end up with a polynomial of $x$ of degree $2^k$. Thus, your claim that the degree of the polynomial can't be too large seems incorrect. Am I missing something?
– D.W.
Jan 19, 2022 at 18:56
• @D.W. I assumed the operations on the integers take at least linear time (not a unit cost model). Thus, if $x^(2^k)$ is computed by repeated squaring, it already takes $\Omega(2^k)$ time (if $|x| > 1$, but it is ensured such input exists). I tried but failed to prove a lower bound for the unit-cost model. Jan 20, 2022 at 1:05
• Correction: actually there could be additional $x$s such that $\mathrm{deg}(p)$ is large but $p(x)$ is small, but there shouldn't be too many such inputs (the coefficients of the polynomial are constant independent of $n$ and $|p(x)| \in \Omega(|x|^{\mathrm{deg}(p)})$). Jan 20, 2022 at 4:23
• Ahh, that makes sense. Thank you for the elaboration.
– D.W.
Jan 20, 2022 at 4:58