Wang, Yongge The algebraic structure of the isomorphic types of tally, polynomial time computable sets. (English) Zbl 1022.03020 Arch. Math. Logic 41, No. 3, 215-244 (2002). MSC: 03D15 03D25 03D30 PDF BibTeX XML Cite \textit{Y. Wang}, Arch. Math. Logic 41, No. 3, 215--244 (2002; Zbl 1022.03020) Full Text: DOI OpenURL
Buhrman, Harry; Hemaspaandra, Edith; Longpré, Luc SPARSE reduces conjunctively to TALLY. (English) Zbl 0830.68042 SIAM J. Comput. 24, No. 4, 673-681 (1995). MSC: 68Q05 68Q30 PDF BibTeX XML Cite \textit{H. Buhrman} et al., SIAM J. Comput. 24, No. 4, 673--681 (1995; Zbl 0830.68042) Full Text: DOI Link OpenURL
Downey, Rod; Gasarch, William; Moses, Michael The structure of the honest polynomial m-degrees. (English) Zbl 0818.03020 Ann. Pure Appl. Logic 70, No. 2, 113-139 (1994). Reviewer: L.Harkleroad (Ithaca) MSC: 03D30 03D15 03D25 PDF BibTeX XML Cite \textit{R. Downey} et al., Ann. Pure Appl. Logic 70, No. 2, 113--139 (1994; Zbl 0818.03020) Full Text: DOI OpenURL
Gavaldà, Ricard; Watanabe, Osamu On the computational complexity of small descriptions. (English) Zbl 0799.68085 SIAM J. Comput. 22, No. 6, 1257-1275 (1993). MSC: 68Q15 68Q05 68Q30 68Q25 PDF BibTeX XML Cite \textit{R. Gavaldà} and \textit{O. Watanabe}, SIAM J. Comput. 22, No. 6, 1257--1275 (1993; Zbl 0799.68085) Full Text: DOI Link OpenURL
Geffert, Viliam Tally versions of the Savitch and Immerman-Szelepcsényi theorems for sublogarithmic space. (English) Zbl 0766.68039 SIAM J. Comput. 22, No. 1, 102-113 (1993). MSC: 68Q15 68Q45 68Q05 PDF BibTeX XML Cite \textit{V. Geffert}, SIAM J. Comput. 22, No. 1, 102--113 (1993; Zbl 0766.68039) Full Text: DOI OpenURL
Tang, Shouwen; Book, Ronald V. Reducibilities on tally and sparse sets. (English) Zbl 0731.68039 RAIRO, Inform. Théor. Appl. 25, No. 3, 293-302 (1991). MSC: 68Q15 03D30 PDF BibTeX XML Cite \textit{S. Tang} and \textit{R. V. Book}, RAIRO, Inform. Théor. Appl. 25, No. 3, 293--302 (1991; Zbl 0731.68039) Full Text: DOI EuDML OpenURL
Downey, Rod On computational complexity and honest polynomial degrees. (English) Zbl 0725.03025 Theor. Comput. Sci. 78, No. 2, 305-317 (1991). Reviewer: C.Calude (Bucureşti) MSC: 03D30 03D15 PDF BibTeX XML Cite \textit{R. Downey}, Theor. Comput. Sci. 78, No. 2, 305--317 (1991; Zbl 0725.03025) Full Text: DOI OpenURL
Tang, Shouwen; Book, Ronald V. Polynomial-time reducibilities and “almost all” oracle sets. (English) Zbl 0719.03020 Theor. Comput. Sci. 81, No. 1, 35-47 (1991). MSC: 03D15 68Q15 68Q05 PDF BibTeX XML Cite \textit{S. Tang} and \textit{R. V. Book}, Theor. Comput. Sci. 81, No. 1, 35--47 (1991; Zbl 0719.03020) Full Text: DOI OpenURL
Rubinstein, Roy S. Self-P-printability and polynomial time turing equivalence to a tally set. (English) Zbl 0737.68034 SIAM J. Comput. 20, No. 6, 1021-1033 (1991). MSC: 68Q15 03D15 68Q30 68Q05 PDF BibTeX XML Cite \textit{R. S. Rubinstein}, SIAM J. Comput. 20, No. 6, 1021--1033 (1991; Zbl 0737.68034) Full Text: DOI OpenURL
Allender, Eric W. P-uniform circuit complexity. (English) Zbl 0697.68031 J. Assoc. Comput. Mach. 36, No. 4, 912-928 (1989). MSC: 68Q25 03D15 68Q05 PDF BibTeX XML Cite \textit{E. W. Allender}, J. Assoc. Comput. Mach. 36, No. 4, 912--928 (1989; Zbl 0697.68031) Full Text: DOI OpenURL
Tang, Shouwen Randomness, tally sets, and complexity classes. (English) Zbl 0691.68049 Combinatorics, computing and complexity, Pap. Int. Symp., Tianjing and Beijing/China 1988, Math. Appl., Chin. Ser. 1, 77-97 (1989). MSC: 68Q25 03D15 PDF BibTeX XML OpenURL
Rolim, José D. P. On the polynomial IO-complexity. (English) Zbl 0689.68069 Inf. Process. Lett. 33, No. 4, 199-204 (1989). MSC: 68Q25 03D15 PDF BibTeX XML Cite \textit{J. D. P. Rolim}, Inf. Process. Lett. 33, No. 4, 199--204 (1989; Zbl 0689.68069) Full Text: DOI OpenURL
Allender, Eric W.; Rubinstein, Roy S. P-printable sets. (English) Zbl 0682.68039 SIAM J. Comput. 17, No. 6, 1193-1202 (1988). Reviewer: A.A.Mullin MSC: 68Q25 68Q05 03D15 03D30 PDF BibTeX XML Cite \textit{E. W. Allender} and \textit{R. S. Rubinstein}, SIAM J. Comput. 17, No. 6, 1193--1202 (1988; Zbl 0682.68039) Full Text: DOI OpenURL
Book, Ronald V.; Ko, Ker-I On sets truth-table reducible to sparse sets. (English) Zbl 0665.68040 SIAM J. Comput. 17, No. 5, 903-919 (1988). Reviewer: G.Wechsung MSC: 68Q25 03D15 68Q05 03D30 PDF BibTeX XML Cite \textit{R. V. Book} and \textit{K.-I Ko}, SIAM J. Comput. 17, No. 5, 903--919 (1988; Zbl 0665.68040) Full Text: DOI OpenURL
Gavaldà, Ricard; Balcázar, José L. Strong and robustly strong polynomial time reducibilities to sparse sets. (English) Zbl 0662.03037 Mathematical foundations of computer science 1988, Proc. 13th Symp., MFCS, Carlsbad/Czech. 1988, Lect. Notes Comput. Sci. 324, 300-308 (1988). Reviewer: R.Downey MSC: 03D30 03D15 03D10 PDF BibTeX XML OpenURL
Book, Ronald V. Sparse sets, tally sets, and polynomial reducibilities. (English) Zbl 0661.03035 Mathematical foundations of computer science 1988, Proc. 13th Symp., MFCS, Carlsbad/Czech. 1988, Lect. Notes Comput. Sci. 324, 1-13 (1988). Reviewer: Phan Dinh Dieu MSC: 03D30 03D15 PDF BibTeX XML OpenURL
Tang, Shouwen; Book, Ronald V. Separating polynomial-time Turing and truth-table reductions by tally sets. (English) Zbl 0658.03025 Automata, languages and programming, Proc. 15th Int. Colloq., Tampere/Finn. 1988, Lect. Notes Comput. Sci. 317, 591-599 (1988). Reviewer: S.P.Yukna MSC: 03D30 68Q25 PDF BibTeX XML OpenURL
Long, Timothy J. Erratum to “On restricting the size of oracles compared with restricting access to oracles”. (English) Zbl 0652.68056 SIAM J. Comput. 17, No. 3, 628 (1988). MSC: 68Q25 68Q05 03D15 PDF BibTeX XML Cite \textit{T. J. Long}, SIAM J. Comput. 17, No. 3, 628 (1988; Zbl 0652.68056) Full Text: DOI OpenURL
Homer, Steven; Long, Timothy J. Honest polynomial degrees and \(P=?NP\). (English) Zbl 0631.68048 Theor. Comput. Sci. 51, 265-280 (1987). Reviewer: D.Lucanu MSC: 68Q25 03D30 03D15 68Q05 PDF BibTeX XML Cite \textit{S. Homer} and \textit{T. J. Long}, Theor. Comput. Sci. 51, 265--280 (1987; Zbl 0631.68048) Full Text: DOI OpenURL
Allender, Eric W. The complexity of sparse sets in P. (English) Zbl 0608.68035 Structure in complexity theory, Proc. Conf., Berkeley/Calif. 1986, Lect. Notes Comput. Sci. 223, 1-11 (1986). Reviewer: D.Mundici MSC: 68Q25 03D15 PDF BibTeX XML OpenURL
Long, Timothy J. On restricting the size of oracles compared with restricting access to oracles. (English) Zbl 0583.68025 SIAM J. Comput. 14, 585-597 (1985). MSC: 68Q25 68Q05 03D15 PDF BibTeX XML Cite \textit{T. J. Long}, SIAM J. Comput. 14, 585--597 (1985; Zbl 0583.68025) Full Text: DOI OpenURL
Selman, Alan L. P-selective sets, tally languages, and the behavior of polynomial time reductibilities on NP (preliminary report). (English) Zbl 0422.03013 Automata, languages and programming, 6th Colloq., Graz 1979, Lect. Notes Comput. Sci. 71, 546-555 (1979). MSC: 03D15 68Q25 PDF BibTeX XML OpenURL
Selman, Alan L. P-selective sets, tally languages, and the behavior of polynomial time reducibilities on NP. (English) Zbl 0405.03018 Math. Syst. Theory 13, 55-65 (1979). MSC: 03D30 03D15 68Q25 PDF BibTeX XML Cite \textit{A. L. Selman}, Math. Syst. Theory 13, 55--65 (1979; Zbl 0405.03018) Full Text: DOI OpenURL