Determinism versus nondeterminism with arithmetic tests and computation: extended abstract

ABSTRACT

For each natural number d we consider a finite structure m_d whose universe is the set of all 0,1-sequence of length n=2^d, each representing a natural number in the set [0,1,...,2ⁿ-1] in binary form. The operations included in the structure are the four constants 0,1,2ⁿ-1,n, multiplication and addition modulo 2ⁿ, the unary function min[2^x, 2ⁿ-1], the binary functions ⌊ x/y⌋ (with ⌊ x/0 ⌋ =0), max(x,y), min(x,y), and the boolean vector operations ∧,∨,- defined on 0,1 sequences of length n by performing the operations on all components simultaneously. These are essentially the arithmetic operations that can be performed on a RAM, with wordlength n, by a single instruction. We show that there exists a term (that is, an algebraic expression) F(x,y) built up from the mentioned operations, with the only free variables x,y, such that for all terms G(y), which is also built up from the mentioned operations, the following holds. For infinitely many positive integers d, there exists an a ∈ m_d such that the following two statements are not equivalent: (i) m_d |= ∃ x, F(x,a), (ii) m_d models G(a)=0. In other words, the question whether an existential statement, depending on the parameter a ∈ m_d is true or not, cannot be decided by evaluating an algebraic expression at a.

Another way of formulating the theorem, in a slightly stronger form, is, that over the structures m_d, quantifier elimination is not possible in the following sense. Let calm be a first-order language with equality, containing function symbols for all of the mentioned arithmetic operations. Then there exists an existential first-order formula φ(y) of calm, containing a single existential quantifier and the only free variable y, such that for each propositional formula P(y) of calm, we have that for infinitely many positive integers d, φ(y) and P(y) are not equivalent on m_d, that is, m_d |= - ∀ y, φ(y) >-> P(y).

We also show that the theorem, in both forms, remains true if the binary operation min [x^y, 2ⁿ-1] is added to the structure m_d. A general theorem is proved as well, which describes sufficient conditions for a set of operations on a sequence of structures k_d, d=1,2,... which guarantees that the analogues of the mentioned theorems holds for the structures k_d too.

References

1. .V. Aho, J.E. Hopcroft, J.D. Ullman, The Design and Analysis of Computer Algorithms, Addison-Wesley, 1974.
2. . Ajtai, Determinism versus Nondeterminism for Linear Time RAMs with Memory Restrictions, Journal of Computer andSystems Science, 65(1): 2--37, (2002)
3. M. Ajtai, Oblivious $RAM$s without cryptographic assumptions, Electronic Colloquium on Computational Complexity (ECCC),17:28, 2010.
4. . Ajtai. Oblivious $RAM$s without cryptographic assumptions,Proceedings of the 42nd ACM Symposium on Theory of Computing, STOC 2010,Cambridge, Massachusetts, USA, 5--8 June 2010, pages 181--190. ACM,2010.
5. . Ajtai, Y. Gurevich, Monotone versus positive, Journal of the ACM (JACM), Vol. 34, Issue 4, Oct. 1987, pp. 1004--1015.
6. E. Artin. Galois Theory, Dover Publications, 1998.(Reprinting of second revised edition of 1944, The University of Notre Dame Press).
7. P. Beame, S. A. Cook, and H. J. Hoover, Log Depth Circuits for Division and Related Problems, SIAM Journal on Computing, 15(4):994--1003, November 1986.
8. . Beame, T. S. Jayram, M. Sacks, Time-space tradeoffs for branching programs, Journal of Computer and Systems Science,63(4):542--572, December 2001.
9. . Beame, M. Sacks, Xiadong Sun, E. Vee, Time-space trade-off lower bounds for randomized computation of decision problems,Journal of ACM, 50(2):154--195,2003.
10. M. Davis, H. Putnam and J. Robinson, Thedecision problem for exponential diophantine equations, Ann. of Math. (2) 74 (1961),425--436. 3. J. P. Jones, Three universal representations of r.e. sets,J. Symbolic Logic 43 (1978), 335--351.
11. W. Hesse, Division is in Uniform $TC^0$, ICALP 2001: 104--114.
12. A. Magid, Differential Galois theory,Notices of the American Mathematical Society 46 (9): 1999.
13. L. Fortnow, Time-space tradoffs for satisfiability, Journal of Computer and System Sciences, 60:337--353, 2000.
14. Ju. V. Matijasevic, Enumerable sets are diophantine, Dokl. Akad.Nauk SSSR 191 (1970), 279--282. English transi.: Soviet Math. Doklady11 (1970), 354--358.
15. . Paul, N. Pippenger, E. Szemerédi, and W. Trotter. On determinism versus nondeterminism and related problems,In Proceedings of the 24th IEEE Symposium on Foundations of Computer Science, pages 429--438. IEEE, New York, 1983.
16. . Takeuti, Proof Theory,North-Holland, Studies in Logic and the Foundations of Mathematics, Vol. 81, Second edition, 1987.
17. . Yao Separating the polynomial time hierarchy by oracles, Proc.26th Annu. IEEE Symp. Found. Comp. Sci. 1--10(1985).

Index Terms

• Theory of computation

  • Computational complexity and cryptography

    • Complexity classes