zbMATH — the first resource for mathematics

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, () · Zbl 0574.68039
[4] {\scJ. 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, (), 63-71
[6] Borodin, A.; Cook, S.; Dymond, P.; Ruzzo, W.; Tompa, M., Two applications of complementation via inductive counting, (), 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, () · Zbl 0411.68058
[12] Immerman, N.; Immerman, N., Nondeterministic space is closed under complement, (), SIAM J. comput., 17, 935-938, (1988) · Zbl 0668.68056
[13] Karp, R.; Lipton, R.; 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, ()
[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)
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.