patternMinor
Computability of equality to zero for a simple language
Viewed 0 times
simpleequalitycomputabilitylanguageforzero
Problem
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.
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.
Solution
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$:
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.
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.
Context
StackExchange Computer Science Q#35969, answer score: 4
Revisions (0)
No revisions yet.