zbMATH — the first resource for mathematics

Unary coded PSPACE-complete languages in \(\mathrm{ASPACE}(\log\log n)\). (English) Zbl 1425.68199
Summary: We study the class of binary coded versions of unary languages that can be accepted by alternating machines with \(\log\log n\) space. We show that there exists a binary PSpace-complete language \(\mathcal {L}\) such that the unary coded version of \(\mathcal {L}\) is in \(\text{\textsc{ASpace}}(\log\log n)\). Consequently, the standard translation between unary languages accepted with \(\log\log n\) space and binary languages accepted with \(\log n\) space works for alternating machines if and only if \(\mathrm{P} = \text{\textsc{PSpace}}\). In general, if a binary language is accepted deterministically in \(2^n \cdot n^{O (1)}\) time and, simultaneously, in \(n^{O(1)}\) space – which covers many PSpace-complete problems – then its unary coded version is accepted by an alternating Turing machine using an initially delimited worktape of size \(\log\log n\). This unexpected power follows from the fact that, with an auxiliary worktape of size \(O(\log\log n)\) on a unary input \(1^n\), an alternating machine can simulate a stack with \(\log n\) bits, representing the contents of the stack by its input head position. The standard push/pop operations on the stack are implemented by moving the head along the input.
68Q45 Formal languages and automata
68Q05 Models of computation (Turing machines, etc.) (MSC2010)
68Q25 Analysis of algorithms and problem complexity
Full Text: DOI
[1] Allender, E., The division breakthroughs, Bull. Eur. Assoc. Theoret. Comput. Sci., 74, 61-77, (2001) · Zbl 1027.68606
[2] Allender, E., Mix Barrington, D., Hesse, W.: Uniform circuits for division: consequences and problems. In: Proc. IEEE Conf. Comput. Complexity, pp. 150-59 (2001)
[3] Bach, E., Shallit, J.: Algorithmic Number Theory. MIT Press, Cambridge (1996) · Zbl 0873.11070
[4] Chandra, A.; Kozen, D.; Stockmeyer, L., Alternation, J. Assoc. Comput. Mach., 28, 114-33, (1981) · Zbl 0473.68043
[5] Chang, R.; Hartmanis, J.; Ranjan, D., Space bounded computations: review and new separation results, Theoret. Comput. Sci., 80, 289-302, (1991) · Zbl 0745.68051
[6] Chiu, A.: Complexity of parallel arithmetic using the Chinese Remainder Representation. Master’s thesis, Univ. Wisconsin-Milwaukee (G. Davida, supervisor) (1995)
[7] Chiu, A.; Davida, G.; Litow, B., Division in logspace-uniform NC1, RAIRO Inform. Théor. Appl., 35, 259-75, (2001) · Zbl 1014.68062
[8] Davida, G.; Litow, B., Fast parallel arithmetic via modular representation, SIAM J. Comput., 20, 756-65, (1991) · Zbl 0736.68040
[9] Dietz, P.; Macarie, I.; Seiferas, J., Bits and relative order from residues, space efficiently, Inform. Process. Lett., 50, 123-27, (1994) · Zbl 0807.68051
[10] Dussart, P., The kth prime is greater than k ⋅ (ln k + ln ln − 1) for k ≥ 2, Math. Comp., 68, 411-15, (1999) · Zbl 0913.11039
[11] Emde Boas, P.: Machine models and simulations. In: Leeuwen, J. (ed.) Handbook of Theoretical Computer Science. Elsevier Science (1989)
[12] Geffert, V., Nondeterministic computations in sublogarithmic space and space constructibility, SIAM J. Comput., 20, 484-98, (1991) · Zbl 0762.68022
[13] Geffert, V., Bridging across the log(n) space frontier, Inf. Comput., 142, 127-58, (1998) · Zbl 0917.68077
[14] Geffert, V., Alternating space is closed under complement and other simulations for sublogarithmic space, Inf. Comput., 253, 163-78, (2017) · Zbl 1364.68215
[15] Geffert, V.; Pardubská, D., Unary coded NP-complete languages in ASPACE(log log n), Int. J. Found. Comput. Sci., 24, 1167-82, (2013) · Zbl 1298.68134
[16] Hartmanis, J.; Immerman, N.; Sewelson, W., Sparse sets in NP-P: EXPTIME versus NEXPTIME, Inf. Control., 65, 158-81, (1985) · Zbl 0586.68042
[17] Hartmanis, J., Lewis, P. II, Stearns, R.: Hierarchies of memory limited computations. In: IEEE Conf. Record on Switching Circuit Theory and Logical Design, pp. 179-90 (1965) · Zbl 0229.02033
[18] Hartmanis, J.; Stearns, R., On the computational complexity of algorithms, Trans. Am. Math. Soc., 117, 285-306, (1965) · Zbl 0131.15404
[19] Hopcroft, J., Motwani, R., Ullman, J.: Introduction to Automata Theory, Languages, and Computation. Addison-Wesley, Reading (2001) · Zbl 0980.68066
[20] Koblitz, N.: A Course in Number Theory and Cryptography, Graduate Texts in Mathematics, vol. 114. Springer, Berlin (1994) · Zbl 0819.11001
[21] Ladner, R.; Lipton, R.; Stockmeyer, L., Alternating pushdown and stack automata, SIAM J. Comput., 13, 135-55, (1984) · Zbl 0538.68039
[22] Liśkiewicz, M.; Reischuk, R., The sublogarithmic alternating space world, SIAM J. Comput., 25, 828-61, (1996) · Zbl 0857.68039
[23] Macarie, I.: Space-efficient deterministic simulation of probabilistic automata. In: Proc. Symp. Theoret. Aspects Comput. Sci., Lect. Notes Comput. Sci., vol. 775, pp 109-22. Springer (1994)
[24] Meyer, A., Stockmeyer, L.: Word problems requiring exponential time. In: Proc. ACM Symp. Theory of Comput., pp 1-9 (1973) · Zbl 0359.68050
[25] Savitch, W., Relationships between nondeterministic and deterministic tape complexities, J. Comput. System Sci., 4, 177-92, (1970) · Zbl 0188.33502
[26] Stockmeyer, L., The polynomial time hierarchy, Theoret. Comput. Sci., 3, 1-22, (1977) · Zbl 0353.02024
[27] Sudborough, I.: Efficient algorithms for path system problems and applications to alternating and time-space complexity classes. In: Proc. IEEE Symp. Found. of Comput. Sci., pp 62-73 (1980)
[28] Szepietowski, A.: Turing Machines with Sublogarithmic Space, Lect. Notes Comput. Sci., vol. 843. Springer, Berlin (1994) · Zbl 0998.68062
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.