Self-reducibility. (English) Zbl 0718.68037

In the paper the ldq-self reducibility, wdq-self reducibility, and logspace self-reducibility are defined (ldq stands for length-decreasing queries and wdq for word-decreasing queries). The properties derived from the definitions regarding the interconnection between uniform and nonuniform complexity classes are used to prove known results and to obtain new ones regarding deterministic time classes, nondeterministic space classes and reducibility to context-free languages. From new results obtained here, we remark the following:
i) Let A be a logspace self-reducible set. If A \(\in NLOG/\log\) then A \(\in NLOG;\)
ii) Let M be a pushdown automaton with no \(\lambda\)-transition which accepts by empty store. There is a set A \(\in LOG(CFL)\) which is logspace self-reducible such that L(M) \(\in DLOG(A)\). Furthermore, if M is deterministic then A \(\in LOG(DCFL)\).
Reviewer: G.Grigoras (Iaşi)


68Q15 Complexity classes (hierarchies, relations among complexity classes, etc.)
68Q45 Formal languages and automata
03D15 Complexity of computation (including implicit computational complexity)
Full Text: DOI


[1] Aho, A. A.; Hopcroft, J. E.; Ullman, J. D., Time and tape complexity of pushdown automaton languages, Inform. and Control, 13, 186-206 (1968) · Zbl 0257.68065
[2] Balcázar, J. L.; Book, R. V.; Schöning, U., The polynomial time hierarchy and sparse oracles, J. Assoc. Comput. Mach., 33, 603-617 (1986) · Zbl 0625.68033
[3] Balcázar, J. L.; Diaz, J.; Gabarró, J., Structural Complexity I, (EATCS Monographs, Vol. 11 (1988), Springer-Verlag: Springer-Verlag New York/Berlin) · Zbl 0574.68039
[4] J. L. Balcázar and U. Schöning, “Logarithmic Advice Classes,” Report de recerca LSI-88-12, Univ. Politècnica de Catalunya, J. Theoret. Comp. Sci., to appear.; J. L. Balcázar and U. Schöning, “Logarithmic Advice Classes,” Report de recerca LSI-88-12, Univ. Politècnica de Catalunya, J. Theoret. Comp. Sci., to appear.
[5] Berman, P., Relationship between density and deterministic complexity of NP-complete languages, (Int. Colloq. Automata, Languages, and Programming. Int. Colloq. Automata, Languages, and Programming, Lect. Notes in Comput. Sci., Vol. 62 (1978), Springer-Verlag: Springer-Verlag New York/Berlin), 63-71 · Zbl 0382.68068
[6] Borodin, A.; Cook, S.; Dymond, P.; Ruzzo, W.; Tompa, M., Two applications of complementation via inductive counting, (Third Structure in Complexity Theory Conference (1988)), 116-125
[7] Chandra, A.; Kozen, D.; Stockmeyer, L., Alternation, J. Assoc. Comput. Mach., 28, 114-133 (1981) · Zbl 0473.68043
[8] Cook, S., Characterizations of pushdown machines in terms of time bounded computers, J. Assoc. Comput. Mach., 18, 4-18 (1971) · Zbl 0222.02035
[9] Fortune, S., A note on sparse complete sets, SIAM J. Comput., 8, 431-433 (1979) · Zbl 0415.68006
[10] Greibach, S., The hardest context-free language, SIAM J. Comput., 2, 304-310 (1973) · Zbl 0278.68073
[11] Harrison, M. A., Introduction to Formal Language Theory, ((1978), Addison-Wesley: Addison-Wesley Reading, MA) · Zbl 0411.68058
[12] Immerman, N., SIAM J. Comput., 17, 935-938 (1988) · Zbl 0668.68056
[13] Karp, R.; Lipton, R., Turing machines that take advice, Enseign. Math., 28, 2, 191-209 (1982) · Zbl 0529.68025
[14] Ko, K., On self-reducibility and weak \(p\)-selectivity, J. Comput. System Sci., 26, 209-221 (1983) · Zbl 0519.68062
[15] Ladner, R., The circuit value problem is logspace complete for \(P\), SIGACT News, 18-20 (January 1975)
[16] Mahaney, S., Sparse complete sets for NP: Solution of a conjecture by Berman and Hartmanis, J. Comput. System Sci., 25, 130-143 (1982) · Zbl 0493.68043
[17] Mahaney, S., Sparse sets and reducibilities, (Book, R., Studies in Complexity Theory (1986), Pitman: Pitman New York)
[18] Meyer, A.; Paterson, M., With what frequency are apparently intractable problems difficult?, M.I.T. Tech. Report TM-126 (1979)
[19] Ruzzo, W.; Simon, J.; Tompa, M., Space-bounded hierarchies and probabilistic computations, J. Comput. System Sci., 28, 216-230 (1984) · Zbl 0573.68021
[20] Sudborough, I. H., On the tape complexity of deterministic context-free languages, J. Assoc. Comput. Mach., 25, 405-414 (1978) · Zbl 0379.68054
[21] Szelepcényi, R., The method of forcing for nondeterministic automata, Bull. EATCS, 33, 96-99 (1987) · Zbl 0664.68082
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.