×

Unary coded NP-complete languages in \(\mathrm{ASpace}(\log \log n)\). (English) Zbl 1298.68134

Summary: We shall show that (i) there exists a binary NP-complete language \(\mathcal L\) such that its unary coded version \({\text{\textsc{un}}}\)-\(\mathcal L\) is in \({\text{\textsc{ASpace}}}(\log \log n)\), (ii) if \(\mathrm P \neq \mathrm{NP}\), there exists a binary language \(\mathcal L\) such that its unary version \({\text{\textsc{un}}}\)-\(\mathcal L\) is in \({\text{\textsc{ASpace}}}(\log \log n)\), while the language \(\mathcal L\) itself is not in \({\text{\textsc{ASpace}}}(\log n)\). As a consequence, under assumption that \(\mathrm P \neq \mathrm{NP}\), the standard space translation between unary and binary languages does not work for alternating machines with small space; the equivalence \(\mathcal L \in {\text{\textsc{ASpace}}}(s(n))\equiv {\text{\textsc{un}}}\)-\(\mathcal L \in {\text{\textsc{ASpace}}}(s(\log n))\) is valid only if \(s(n) \in {\Omega}(n)\). This is quite different from deterministic and nondeterministic machines, for which the corresponding equivalence holds for each \(s(n) \in {\Omega}(\log n)\), and hence for \(s(\log n) \in {\Omega}(\log \log n)\). Under assumption that \(\mathrm{NP} \neq {\mathrm{co}}\text{-}\mathrm{NP}\), we also show that binary versions of unary languages in \({\text{\textsc{ASpace}}}(\log \log n)\) form a complexity class not contained in NP.

MSC:

68Q45 Formal languages and automata
68Q15 Complexity classes (hierarchies, relations among complexity classes, etc.)
68Q17 Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Agrawal M., Math. 160 pp 781– (2004)
[2] Allender E., Bull. Eur. Assoc. Theoret. Comput. Sci. 74 pp 61– (2001)
[3] DOI: 10.1145/322234.322243 · Zbl 0473.68043 · doi:10.1145/322234.322243
[4] DOI: 10.1016/0304-3975(91)90391-E · Zbl 0745.68051 · doi:10.1016/0304-3975(91)90391-E
[5] Chiu A., Appl. 35 pp 259– (2001)
[6] DOI: 10.1016/0020-0190(94)00021-2 · Zbl 0807.68051 · doi:10.1016/0020-0190(94)00021-2
[7] Geffert V., Comput. 142 pp 127– (1998)
[8] DOI: 10.1016/S0304-3975(02)00402-4 · Zbl 1038.68053 · doi:10.1016/S0304-3975(02)00402-4
[9] DOI: 10.1137/0222011 · Zbl 0767.68039 · doi:10.1137/0222011
[10] DOI: 10.1137/S0097539793252444 · Zbl 0857.68039 · doi:10.1137/S0097539793252444
[11] DOI: 10.1016/S0022-0000(70)80006-X · Zbl 0188.33502 · doi:10.1016/S0022-0000(70)80006-X
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. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.