7
$\begingroup$

Suppose we have a tree in which leaves are labeled with a set of numbers $L$, and internal nodes with a set of operations $O$.

In particular $L$ can be $\mathbb{N}, \mathbb{Z}$ or $\mathbb{Q}$, and can optionally contain $\pi$ and/or $e$. $O$ can be any subset of $\{+,-,\cdot,/,\hat\ \}$.

Is equality with zero decidable? Are sign comparisons decidable? If so, are they feasible?

"Invalid" operations ($0/0$, $0^0$, ...) produce $NaN$, $NaN \neq 0$ and $NaN$ propagates through computations as usual.

Some combinations are trivial: if we restrict ourselves to field operations, and don't include either $\pi$ or $e$ in $L$ then we can just compute the resulting fraction and be done with it. Or if we restrict to $\mathbb{Z} \cup \{\pi\}$ and $\{+,-,\cdot\}$ we can compute the polynomial and check the coefficents. On the other hand powers (and hence $n$-th roots) and $\pi$ and $e$ make things considerably harder.

The "equality with zero" problem is an instance of the constant problem.

$\endgroup$
4
$\begingroup$

If you use the operators $\{+,-,\times,/\}$ (i.e., you don't included the power operator), then all of your problems are likely decidable.

Testing equality with zero

For instance, let's consider $L = \mathbb{Z} \cup \{\pi\}$. Then you can treat $\pi$ as a formal symbol, so that each leaf is a polynomial in $\mathbb{Z}[\pi]$ (e.g., the integer $5$ is the constant polynomial $5$; $\pi$ is the polynomial $\pi+0$ of degree 1). Now you can express the tree as a rational polynomial over $\mathbb{Z}$, with $\pi$ as the formal unknown.

Suppose this polynomial is $p(\pi)/q(\pi)$. Test whether $p(\pi)$ is the zero polynomial (degree $-\infty$). If it is not the zero polynomial, then the expression is not equal to zero. If $p(\pi)$ is the zero polynomial, and $q(\pi)$ is not the zero polynomial, then the expression is equal to zero. The correctness of this procedure follows from the fact that $\pi$ is transcendental.

What's the complexity of this procedure? The answer depends on the computational model. Let's assume that each operator as taking constant time to evaluate (regardless of the size of the operands). Then the complexity depends on the size of the resulting polynomials. The degree of the polynomial can grow exponentially with the depth of the tree, so if you build the polynomial recursively and express it explicitly (in coefficient form), the running time will be at most exponential in the depth of the tree. Fortunately, the degree grows at most linearly in the number of leaves in the tree, so the running time of a deterministic algorithm is linear in the size of the tree.

Therefore, assuming a straightforward representation of the tree and a simplistic computational model, this gives you a linear time algorithm for zero testing when the operators are $\{+,-,\times,/\}$.

This procedure works not just for $L=\mathbb{Z} \cup \{\pi\}$, but also for $\mathbb{N} \cup \{\pi\}$ and $\mathbb{Q} \cup \{\pi\}$.

The same procedure also works for $L=\mathbb{Q} \cup \{\pi,e\}$, if we can assume a reasonable conjecture: that $\pi$ and $e$ are algebraically independent. It is not known whether this conjecture is correct, but it seems likely. Anyway, here's the approach. We treat the polynomial as a multivariate polynomial over two unknowns $\pi,e$ instead of one unknown, but everything carries over as before, given the algebraic independence of $\pi$ and $e$. It also works for $L=\mathbb{Z} \cup \{\pi,e\}$ and $L=\mathbb{N} \cup \{\pi,e\}$, too, again, assuming the conjecture.

If you wanted to get fancy, you could use randomized algorithms for polynomial identity testing. If $L = \mathbb{Z} \cup \{\pi\}$, they'll amount to the following: choose a random prime $r$ and a random integer $s_{\pi} \in \{0,\dots,r-1\}$; replace each instance of $\pi$ with $s_{\pi}$; and then check whether the resulting expression evaluates to $0 \bmod r$. (If you have both $\pi$ and $e$, you'll pick two random integers $s_{\pi}$ and $s_e$.) You can repeat this test multiple times. If this procedure ever gives you something non-zero (modulo $r$), then the original expression is certainly non-zero. If it always gives you zero (modulo $r$), then with high probability the original expression is equal to zero. This may be more efficient in some computational models (e.g., where the time to evaluate a single operator is dependent on the size of the operands).

Sign comparison

You can also find the sign of the expression using similar procedures (again, assuming you have excluded the ^ operator, and again, assuming that $\pi$ and $e$ are algebraically independent). Evaluate the expression as a rational polynomial $p(\pi,e)/q(\pi,e)$ over $\mathbb{Q}[\pi,e]$. Assume you have determined that $p(\pi,e)/q(\pi,e) \ne 0$ and $q(\pi,e) \ne 0$. You want to know whether $p(\pi,e)/q(\pi,e) > 0$ or not.

Here is one approach. Note that $p(\pi,e)/q(\pi,e) > 0$ iff $p(\pi,e) \cdot q(\pi,e) > 0$. Therefore, we can form a new polynomial $r(\pi,e) = p(\pi,e) \cdot q(\pi,e)$ and reduce this to the problem of evaluating the sign of $r(\pi,e)$. Basically, we need to evaluate the sign of a rational polynomial in $\pi$ and $e$. We know this evaluates to something non-zero.

One approach is to compute $\pi$ and $e$ to $k$ bits of precision, and then evaluate $r(\pi,e)$ accordingly, gaining lower and upper bounds on $r(\pi,e)$. If 0 is included within this interval, double $k$, until the lower bound is strictly positive or the lower bound is strictly negative.

What's the complexity of this approach? If $|r(\pi,e)|$ evaluates to a value $\epsilon$, then I think the running time will be polynomial in the size of the input and in $\lg 1/\epsilon$.

There may be a better algorithm, but this is the best I can come up with right now.

Conclusion

The takeaway is that the power operator (^) is the real source of difficulty. Without the power operator, all of your problems can be solved without too much difficulty (assuming a reasonable conjecture).

$\endgroup$
  • 1
    $\begingroup$ It is not known that $\pi$ and $e$ are algebraically independent. $\endgroup$ – Yuval Filmus Jan 6 '15 at 9:09
  • $\begingroup$ The sign algorithm looks interesting, thank you! Anyway, as Yuval said, we don't know about independence $\endgroup$ – miniBill Jan 6 '15 at 9:54
4
$\begingroup$

This is a rather tricky question! As you seem to understand, the real issue is the presence of $\hat{}$. It is intimately related to a well known conjecture: Schanuel's conjecture, which states that, essentially, there are no non-trivial algebraic relationships between $\pi$ and $e$.

The (expected) positive answer to this conjecture would give you a decision procedure for comparison with $0$:

  • Reduce the expression using algebraic equalities (e.g. $(x^y)^z = x^{yz}$ etc.)
  • Separate the terms with exponents and the terms without.
  • Check that the base ($x$ in $x^y$) of the terms with exponents are all linearly independent.
  • The term is 0 iff it is trivial i.e. it reduces to 0 by algebraic operations.

A related question is Tarski's exponential function problem which involves variables. However it is relatively simple to reduce concrete expressions with exponents to functions with variables given the Lindemann-Wierstrass theorem.

Edit: I don't know anything about the actual complexity of the problem, though. Note that it strongly depends on your computational model e.g. whether arithmetic operations constant time.

Edit 2: I made a crucial mistake: it's not the base $x$ in $x^y$ that needs to be taken but rather $y\ln(x)$, which is much harder to check for linear independence.

$\endgroup$
  • $\begingroup$ My computational model is a real computer (with infinite memory of course) $\endgroup$ – miniBill Jan 5 '15 at 16:35
  • $\begingroup$ How about stuff like $(((pi-e)^pi)+pi-e^(1/2)$? How would you reduce it? $\endgroup$ – miniBill Jan 5 '15 at 19:40
  • 1
    $\begingroup$ I assume you're asking about the expression $(\pi - e)^\pi+\pi-e^{1/2}$. In that case it is already "reduced". All you need to check is that $(\pi - e)\ln(\pi)$, $\ln(\pi)$ and $1/2$ are linearly independent, and deduce that the expression is non-zero as their exponentials must be algebraically independent. $\endgroup$ – cody Jan 5 '15 at 21:00
  • $\begingroup$ How do you algorithmically check for linear independence? $\endgroup$ – miniBill Jan 6 '15 at 9:56
  • $\begingroup$ Hmmm. I'm not sure actually. It's rather easy to show that $e^\pi$ is transcendental assuming the conjecture, but I'm stumped about $\pi\ln(\pi - e)$. I'll edit my answer. $\endgroup$ – cody Jan 6 '15 at 15:37

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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