1
$\begingroup$

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

$\endgroup$
3
  • 1
    $\begingroup$ 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$. $\endgroup$
    – D.W.
    Jan 17, 2022 at 15:23
  • 1
    $\begingroup$ 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. $\endgroup$
    – D.W.
    Jan 17, 2022 at 15:30
  • 1
    $\begingroup$ Overall, I doubt it can be done in polynomial time with those operators, though I can't prove it. $\endgroup$
    – D.W.
    Jan 17, 2022 at 15:36

1 Answer 1

2
$\begingroup$

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.

$\endgroup$
4
  • $\begingroup$ 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? $\endgroup$
    – D.W.
    Jan 19, 2022 at 18:56
  • $\begingroup$ @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. $\endgroup$
    – pcpthm
    Jan 20, 2022 at 1:05
  • $\begingroup$ 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)})$). $\endgroup$
    – pcpthm
    Jan 20, 2022 at 4:23
  • $\begingroup$ Ahh, that makes sense. Thank you for the elaboration. $\endgroup$
    – D.W.
    Jan 20, 2022 at 4:58

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.