Grandoni, Fabrizio; Laekhanukit, Bundit; Li, Shi \(O(\log^2 k/\log\log k)\)-approximation algorithm for directed Steiner tree: a tight quasi-polynomial-time algorithm. (English) Zbl 1433.68614 Charikar, Moses (ed.) et al., Proceedings of the 51st annual ACM SIGACT symposium on theory of computing, STOC ’19, Phoenix, AZ, USA, June 23–26, 2019. New York, NY: Association for Computing Machinery (ACM). 253-264 (2019). MSC: 68W25 68Q17 68R10 68W40 PDF BibTeX XML Cite \textit{F. Grandoni} et al., in: Proceedings of the 51st annual ACM SIGACT symposium on theory of computing, STOC '19, Phoenix, AZ, USA, June 23--26, 2019. New York, NY: Association for Computing Machinery (ACM). 253--264 (2019; Zbl 1433.68614) Full Text: DOI arXiv OpenURL
Döcker, Janosch; Linz, Simone; Semple, Charles Displaying trees across two phylogenetic networks. (English) Zbl 1435.68231 Theor. Comput. Sci. 796, 129-146 (2019). MSC: 68R10 68Q17 68Q25 92D15 PDF BibTeX XML Cite \textit{J. Döcker} et al., Theor. Comput. Sci. 796, 129--146 (2019; Zbl 1435.68231) Full Text: DOI arXiv OpenURL
Beckmann, Arnold; Buss, Samuel R.; Friedman, Sy-David Safe recursive set functions. (English) Zbl 1357.03075 J. Symb. Log. 80, No. 3, 730-762 (2015). Reviewer: Leon Harkleroad (Bowdoinham) MSC: 03D65 03D15 03D10 68Q15 PDF BibTeX XML Cite \textit{A. Beckmann} et al., J. Symb. Log. 80, No. 3, 730--762 (2015; Zbl 1357.03075) Full Text: DOI Link OpenURL
Glaßer, Christian; Travers, Stephen; Wagner, Klaus W. Perfect correspondences between dot-depth and polynomial-time hierarchies. (English) Zbl 1410.68136 J. Comput. Syst. Sci. 80, No. 7, 1359-1373 (2014). MSC: 68Q15 68Q45 PDF BibTeX XML Cite \textit{C. Glaßer} et al., J. Comput. Syst. Sci. 80, No. 7, 1359--1373 (2014; Zbl 1410.68136) Full Text: DOI OpenURL
Leivant, Daniel M. Alternating Turing machines for inductive languages. (English) Zbl 1322.03030 Log. Methods Comput. Sci. 9, No. 3, Paper No. 31, 12 p. (2013). Reviewer: Stela K. Nikolova (Sofia) MSC: 03D10 03D60 03D70 PDF BibTeX XML Cite \textit{D. M. Leivant}, Log. Methods Comput. Sci. 9, No. 3, Paper No. 31, 12 p. (2013; Zbl 1322.03030) Full Text: DOI arXiv OpenURL
Goldreich, Oded; Zuckerman, David Another proof that \(\mathcal{BPP}\subseteq \mathcal{PH}\) (and more). (English) Zbl 1343.68085 Goldreich, Oded (ed.), Studies in complexity and cryptography. Miscellanea on the interplay between randomness and computation. In collaboration with Lidor Avigad, Mihir Bellare, Zvika Brakerski, Shafi Goldwasser, Shai Halevi, Tali Kaufman, Leonid Levin, Noam Nisan, Dana Ron, Madhu Sudan, Luca Trevisan, Salil Vadhan, Avi Wigderson, David Zuckerman. Berlin: Springer (ISBN 978-3-642-22669-4/pbk). Lecture Notes in Computer Science 6650, 40-53 (2011). MSC: 68Q15 PDF BibTeX XML Cite \textit{O. Goldreich} and \textit{D. Zuckerman}, Lect. Notes Comput. Sci. 6650, 40--53 (2011; Zbl 1343.68085) Full Text: DOI OpenURL
Hemmerling, Armin Observations on complete sets between linear time and polynomial time. (English) Zbl 1213.68295 Inf. Comput. 209, No. 2, 173-182 (2011). MSC: 68Q15 PDF BibTeX XML Cite \textit{A. Hemmerling}, Inf. Comput. 209, No. 2, 173--182 (2011; Zbl 1213.68295) Full Text: DOI OpenURL
Buchfuhrer, David; Umans, Christopher The complexity of Boolean formula minimization. (English) Zbl 1218.68089 J. Comput. Syst. Sci. 77, No. 1, 142-153 (2011). MSC: 68Q25 90C99 PDF BibTeX XML Cite \textit{D. Buchfuhrer} and \textit{C. Umans}, J. Comput. Syst. Sci. 77, No. 1, 142--153 (2011; Zbl 1218.68089) Full Text: DOI Link OpenURL
Buhrman, Harry; Fortnow, Lance; Koucký, Michal; Rogers, John D.; Vereshchagin, Nikolay Does the polynomial hierarchy collapse if onto functions are invertible? (English) Zbl 1183.68296 Theory Comput. Syst. 46, No. 1, 143-156 (2010). MSC: 68Q17 68Q30 PDF BibTeX XML Cite \textit{H. Buhrman} et al., Theory Comput. Syst. 46, No. 1, 143--156 (2010; Zbl 1183.68296) Full Text: DOI OpenURL
Viola, Emanuele On approximate majority and probabilistic time. (English) Zbl 1217.68101 Comput. Complexity 18, No. 3, 337-375 (2009). MSC: 68Q10 68Q15 68Q17 PDF BibTeX XML Cite \textit{E. Viola}, Comput. Complexity 18, No. 3, 337--375 (2009; Zbl 1217.68101) Full Text: DOI Link OpenURL
Glaßer, Christian; Travers, Stephen Machines that can output empty words. (English) Zbl 1192.68320 Theory Comput. Syst. 44, No. 3, 369-390 (2009). MSC: 68Q17 68Q45 PDF BibTeX XML Cite \textit{C. Glaßer} and \textit{S. Travers}, Theory Comput. Syst. 44, No. 3, 369--390 (2009; Zbl 1192.68320) Full Text: DOI OpenURL
Haviv, Ishay; Regev, Oded; Ta-Shma, Amnon On the hardness of satisfiability with bounded occurrences in the polynomial-time hierarchy. (English) Zbl 1213.68311 Theory Comput. 3, Paper No. 3, 45-60 (2007). MSC: 68Q17 03D15 68Q15 PDF BibTeX XML Cite \textit{I. Haviv} et al., Theory Comput. 3, Paper No. 3, 45--60 (2007; Zbl 1213.68311) Full Text: DOI arXiv OpenURL
Chen, Jianer; Huang, Xiuzhen; Kanj, Iyad A.; Xia, Ge Polynomial time approximation schemes and parameterized complexity. (English) Zbl 1109.68135 Discrete Appl. Math. 155, No. 2, 180-193 (2007). MSC: 68W25 PDF BibTeX XML Cite \textit{J. Chen} et al., Discrete Appl. Math. 155, No. 2, 180--193 (2007; Zbl 1109.68135) Full Text: DOI OpenURL
Williams, Ryan Inductive time-space lower bounds for SAT and related problems. (English) Zbl 1125.68060 Comput. Complexity 15, No. 4, 433-470 (2006). MSC: 68Q17 PDF BibTeX XML Cite \textit{R. Williams}, Comput. Complexity 15, No. 4, 433--470 (2006; Zbl 1125.68060) Full Text: DOI OpenURL
Diehl, Scott; Van Melkebeek, Dieter Time-space lower bounds for the polynomial-time hierarchy on randomized machines. (English) Zbl 1120.68055 SIAM J. Comput. 36, No. 3, 563-594 (2006). MSC: 68Q17 68Q10 68Q15 PDF BibTeX XML Cite \textit{S. Diehl} and \textit{D. Van Melkebeek}, SIAM J. Comput. 36, No. 3, 563--594 (2006; Zbl 1120.68055) Full Text: DOI OpenURL
Köbler, Johannes; Lindner, Wolfgang The complexity of learning concept classes with polynomial general dimension. (English) Zbl 1086.68064 Theor. Comput. Sci. 350, No. 1, 49-62 (2006). MSC: 68Q32 PDF BibTeX XML Cite \textit{J. Köbler} and \textit{W. Lindner}, Theor. Comput. Sci. 350, No. 1, 49--62 (2006; Zbl 1086.68064) Full Text: DOI Link OpenURL
Guruswami, Venkatesan; Micciancio, Daniele; Regev, Oded The complexity of the covering radius problem. (English) Zbl 1085.68063 Comput. Complexity 14, No. 2, 90-121 (2005). MSC: 68Q17 68Q25 11H06 11H31 94B05 94B75 PDF BibTeX XML Cite \textit{V. Guruswami} et al., Comput. Complexity 14, No. 2, 90--121 (2005; Zbl 1085.68063) Full Text: DOI OpenURL
Niggl, Karl-Heinz Control structures in programs and computational complexity. (English) Zbl 1064.68029 Ann. Pure Appl. Logic 133, No. 1-3, 247-273 (2005). MSC: 68N30 68Q15 68N15 68N18 03D20 PDF BibTeX XML Cite \textit{K.-H. Niggl}, Ann. Pure Appl. Logic 133, No. 1--3, 247--273 (2005; Zbl 1064.68029) Full Text: DOI OpenURL
Cai, Jin-Yi; Watanabe, Osamu Relativized collapsing between BPP and PH under stringent oracle access. (English) Zbl 1178.68271 Inf. Process. Lett. 90, No. 3, 147-154 (2004). MSC: 68Q15 PDF BibTeX XML Cite \textit{J.-Y. Cai} and \textit{O. Watanabe}, Inf. Process. Lett. 90, No. 3, 147--154 (2004; Zbl 1178.68271) Full Text: DOI OpenURL
Cai, Jin-Yi; Charles, Denis; Pavan, A.; Sengupta, Samik On higher Arthur-Merlin classes. (English) Zbl 1101.68594 Int. J. Found. Comput. Sci. 15, No. 1, 3-19 (2004). MSC: 68Q15 PDF BibTeX XML Cite \textit{J.-Y. Cai} et al., Int. J. Found. Comput. Sci. 15, No. 1, 3--19 (2004; Zbl 1101.68594) Full Text: DOI OpenURL
Kołodziejczyk, Leszek Aleksander A finite model-theoretical proof of a property of bounded query classes within PH. (English) Zbl 1081.03027 J. Symb. Log. 69, No. 4, 1105-1116 (2004). MSC: 03C13 68Q15 68Q19 PDF BibTeX XML Cite \textit{L. A. Kołodziejczyk}, J. Symb. Log. 69, No. 4, 1105--1116 (2004; Zbl 1081.03027) Full Text: DOI OpenURL
Kristiansen, L.; Niggl, K.-H. On the computational complexity of imperative programming languages. (English) Zbl 1048.03030 Theor. Comput. Sci. 318, No. 1-2, 139-161 (2004). MSC: 03D10 03D15 03D20 68Q15 68N15 PDF BibTeX XML Cite \textit{L. Kristiansen} and \textit{K. H. Niggl}, Theor. Comput. Sci. 318, No. 1--2, 139--161 (2004; Zbl 1048.03030) Full Text: DOI Link OpenURL
Selivanov, Victor L. Relating automata-theoretic hierarchies to complexity-theoretic hierarchies. (English) Zbl 1029.03027 Theor. Inform. Appl. 36, No. 1, 29-42 (2002). Reviewer: Jerzy Mycka (Lublin) MSC: 03D15 03D05 03D55 68Q15 68Q45 PDF BibTeX XML Cite \textit{V. L. Selivanov}, Theor. Inform. Appl. 36, No. 1, 29--42 (2002; Zbl 1029.03027) Full Text: DOI Numdam Numdam EuDML OpenURL
Sureson, Claude Analytic sets in descriptive set theory and NP sets in complexity theory. (English) Zbl 1004.03038 Fundam. Inform. 50, No. 1, 77-110 (2002). MSC: 03E15 03D15 68Q15 PDF BibTeX XML Cite \textit{C. Sureson}, Fundam. Inform. 50, No. 1, 77--110 (2002; Zbl 1004.03038) OpenURL
Beigel, Richard; Chang, Richard Commutative queries. (English) Zbl 1007.03040 Inf. Comput. 166, No. 1, 71-91 (2001). MSC: 03D15 68Q15 03D10 03B25 PDF BibTeX XML Cite \textit{R. Beigel} and \textit{R. Chang}, Inf. Comput. 166, No. 1, 71--91 (2001; Zbl 1007.03040) Full Text: DOI OpenURL
Reith, S.; Wagner, K. W. On boolean lowness and boolean highness. (English) Zbl 0974.68064 Theor. Comput. Sci. 261, No. 2, 305-321 (2001). MSC: 68Q15 03D15 PDF BibTeX XML Cite \textit{S. Reith} and \textit{K. W. Wagner}, Theor. Comput. Sci. 261, No. 2, 305--321 (2001; Zbl 0974.68064) Full Text: DOI OpenURL
Fortnow, Lance Relativized worlds with an infinite hierarchy. (English) Zbl 1002.68060 Inf. Process. Lett. 69, No. 6, 309-313 (1999). MSC: 68Q15 PDF BibTeX XML Cite \textit{L. Fortnow}, Inf. Process. Lett. 69, No. 6, 309--313 (1999; Zbl 1002.68060) Full Text: DOI OpenURL
Fenner, Stephen; Green, Frederic; Homer, Steven; Pruim, Randall Determining acceptance possibility for a quantum computation is hard for the polynomial hierarchy. (English) Zbl 0964.68011 Proc. R. Soc. Lond., Ser. A, Math. Phys. Eng. Sci. 455, No. 1991, 3953-3966 (1999). MSC: 68N01 81P68 PDF BibTeX XML Cite \textit{S. Fenner} et al., Proc. R. Soc. Lond., Ser. A, Math. Phys. Eng. Sci. 455, No. 1991, 3953--3966 (1999; Zbl 0964.68011) Full Text: DOI arXiv OpenURL
Borchert, Bernd; Kuske, Dietrich; Stephan, Frank On existentially first-order definable languages and their relation to NP. (English) Zbl 0949.03035 Theor. Inform. Appl. 33, No. 3, 259-269 (1999). Reviewer: Gheorghe Grigoras (Iaşi) MSC: 03D15 68Q15 03D05 PDF BibTeX XML Cite \textit{B. Borchert} et al., Theor. Inform. Appl. 33, No. 3, 259--269 (1999; Zbl 0949.03035) Full Text: DOI Numdam EuDML OpenURL
Bellantoni, Stephen J.; Niggl, Karl-Heinz Ranking primitive recursions: The low Grzegorczyk classes revisited. (English) Zbl 0939.03042 SIAM J. Comput. 29, No. 2, 401-415 (1998). MSC: 03D20 68Q15 03D15 PDF BibTeX XML Cite \textit{S. J. Bellantoni} and \textit{K.-H. Niggl}, SIAM J. Comput. 29, No. 2, 401--415 (1998; Zbl 0939.03042) Full Text: DOI OpenURL
Borchert, Bernd; Kuske, Dietrich; Stephan, Frank On existentially first-order definable languages and their relation to NP. (English) Zbl 0917.68076 Larsen, Kim G. (ed.) et al., Automata, languages and programming. 25th international colloquium, ICALP ’98. Aalborg, Denmark, July 13–17, 1998. Proceedings. Berlin: Springer. Lect. Notes Comput. Sci. 1443, 17-28 (1998). MSC: 68Q15 68Q45 PDF BibTeX XML Cite \textit{B. Borchert} et al., Lect. Notes Comput. Sci. 1443, 17--28 (1998; Zbl 0917.68076) OpenURL
Baier, Herbert; Wagner, Klaus W. The analytic polynomial-time hierarchy. (English) Zbl 0920.03051 Math. Log. Q. 44, No. 4, 529-544 (1998). Reviewer: Tao Renji (Beijing) MSC: 03D15 68Q15 03D20 68Q10 PDF BibTeX XML Cite \textit{H. Baier} and \textit{K. W. Wagner}, Math. Log. Q. 44, No. 4, 529--544 (1998; Zbl 0920.03051) Full Text: DOI OpenURL
Berg, Christer; Ulfberg, Staffan A lower bound for perceptrons and an oracle separation of the \(PP^{PH}\) hierarchy. (English) Zbl 0912.68001 J. Comput. Syst. Sci. 56, No. 3, 263-271 (1998). Reviewer: Nikolay Y.Tikhonenko (Odessa) MSC: 68M07 PDF BibTeX XML Cite \textit{C. Berg} and \textit{S. Ulfberg}, J. Comput. Syst. Sci. 56, No. 3, 263--271 (1998; Zbl 0912.68001) Full Text: DOI OpenURL
Köbler, Johannes; Watanabe, Osamu New collapse consequences of NP having small circuits. (English) Zbl 0920.03052 SIAM J. Comput. 28, No. 1, 311-324 (1998). Reviewer: Tao Renji (Beijing) MSC: 03D15 68Q15 68Q10 03D10 PDF BibTeX XML Cite \textit{J. Köbler} and \textit{O. Watanabe}, SIAM J. Comput. 28, No. 1, 311--324 (1998; Zbl 0920.03052) Full Text: DOI OpenURL
Bellantoni, Stephen J. Ranking arithmetic proofs by implicit ramification. (English) Zbl 0890.03034 Beame, Paul W. (ed.) et al., Proof complexity and feasible arithmetics. Papers from the DIMACS workshop, Rutgers, NJ, USA, April 21–24, 1996. Providence, RI: American Mathematical Society. DIMACS, Ser. Discrete Math. Theor. Comput. Sci. 39, 37-57 (1998). MSC: 03F30 03F20 68Q15 03D20 03F07 PDF BibTeX XML Cite \textit{S. J. Bellantoni}, DIMACS, Ser. Discrete Math. Theor. Comput. Sci. 39, 37--57 (1998; Zbl 0890.03034) OpenURL
Di Paola, Robert A.; Montagna, Franco Progressions of theories of bounded arithmetic. (English) Zbl 0881.03029 Sorbi, Andrea (ed.), Complexity, logic, and recursion theory. New York, NY: Marcel Dekker. Lect. Notes Pure Appl. Math. 187, 123-156 (1997). Reviewer: R.Kossak (New York) MSC: 03F30 03F15 68Q15 PDF BibTeX XML Cite \textit{R. A. Di Paola} and \textit{F. Montagna}, Lect. Notes Pure Appl. Math. 187, 123--156 (1997; Zbl 0881.03029) OpenURL
Cucker, Felipe Machines over the reals and non-uniformity. (English) Zbl 0941.03038 Math. Log. Q. 43, No. 2, 143-157 (1997). MSC: 03D10 68Q15 03D15 68Q17 68Q05 68Q25 03B25 PDF BibTeX XML Cite \textit{F. Cucker}, Math. Log. Q. 43, No. 2, 143--157 (1997; Zbl 0941.03038) Full Text: DOI OpenURL
Zambella, Domenico Notes on polynomially bounded arithmetic. (English) Zbl 0864.03039 J. Symb. Log. 61, No. 3, 942-966 (1996). Reviewer: R.Kossak (New York) MSC: 03F35 03C62 03D15 PDF BibTeX XML Cite \textit{D. Zambella}, J. Symb. Log. 61, No. 3, 942--966 (1996; Zbl 0864.03039) Full Text: DOI OpenURL
Bochernikov, B. Ya. On certain models of bounded arithmetic. (Russian) Zbl 0871.03026 Dal’nevost. Mat. Sb. 1, 5-9 (1995). Reviewer: R.Kossak (New York) MSC: 03C62 03D15 68Q15 PDF BibTeX XML Cite \textit{B. Ya. Bochernikov}, Dal'nevost. Mat. Sb. 1, 5--9 (1995; Zbl 0871.03026) OpenURL
Naik, Ashish V.; Regan, Kenneth W.; Sivakumar, D. On quasilinear-time complexity theory. (English) Zbl 0873.68070 Theor. Comput. Sci. 148, No. 2, 325-349 (1995). MSC: 68Q15 PDF BibTeX XML Cite \textit{A. V. Naik} et al., Theor. Comput. Sci. 148, No. 2, 325--349 (1995; Zbl 0873.68070) Full Text: DOI OpenURL
Buss, Samuel R. Relating the bounded arithmetic and polynomial time hierarchies. (English) Zbl 0829.03035 Ann. Pure Appl. Logic 75, No. 1-2, 67-77 (1995). MSC: 03F30 PDF BibTeX XML Cite \textit{S. R. Buss}, Ann. Pure Appl. Logic 75, No. 1--2, 67--77 (1995; Zbl 0829.03035) Full Text: DOI OpenURL
Long, T. J.; Sheu, Ming-Jye A refinement of the low and high hierarchies. (English) Zbl 0849.68038 Math. Syst. Theory 28, No. 4, 299-327 (1995). MSC: 68Q15 PDF BibTeX XML Cite \textit{T. J. Long} and \textit{M.-J. Sheu}, Math. Syst. Theory 28, No. 4, 299--327 (1995; Zbl 0849.68038) Full Text: DOI OpenURL
Li, Hongzhou; Li, Guanying Nonuniform lowness and strong nonuniform lowness. (English) Zbl 0837.68036 J. Comput. Sci. Technol. 10, No. 3, 253-259 (1995). MSC: 68Q15 PDF BibTeX XML Cite \textit{H. Li} and \textit{G. Li}, J. Comput. Sci. Technol. 10, No. 3, 253--259 (1995; Zbl 0837.68036) Full Text: DOI OpenURL
Ignjatović, Aleksandar Delineating classes of computational complexity via second order theories with weak set existence principles. I. (English) Zbl 0819.03030 J. Symb. Log. 60, No. 1, 103-121 (1995). MSC: 03D15 68Q15 03F30 03D20 PDF BibTeX XML Cite \textit{A. Ignjatović}, J. Symb. Log. 60, No. 1, 103--121 (1995; Zbl 0819.03030) Full Text: DOI OpenURL
Gottlob, Georg NP trees and Carnap’s modal logic. (English) Zbl 0886.68069 J. Assoc. Comput. Mach. 42, No. 2, 421-427 (1995). MSC: 68Q15 PDF BibTeX XML Cite \textit{G. Gottlob}, J. Assoc. Comput. Mach. 42, No. 2, 421--427 (1995; Zbl 0886.68069) Full Text: DOI OpenURL
Ferreira, Fernando Binary models generated by their tally part. (English) Zbl 0803.03039 Arch. Math. Logic 33, No. 4, 283-289 (1994). Reviewer: F.Ferreira (Lisboa) MSC: 03F30 03C62 PDF BibTeX XML Cite \textit{F. Ferreira}, Arch. Math. Logic 33, No. 4, 283--289 (1994; Zbl 0803.03039) Full Text: DOI OpenURL
Sheu, Ming-Jye; Long, Timothy J. The extended low hierarchy is an infinite hierarchy. (English) Zbl 0819.68055 SIAM J. Comput. 23, No. 3, 488-509 (1994). MSC: 68Q15 68Q05 PDF BibTeX XML Cite \textit{M.-J. Sheu} and \textit{T. J. Long}, SIAM J. Comput. 23, No. 3, 488--509 (1994; Zbl 0819.68055) Full Text: DOI OpenURL
Stewart, Iain A. Context-sensitive transitive closure operators. (English) Zbl 0799.03043 Ann. Pure Appl. Logic 66, No. 3, 277-301 (1994). Reviewer: U.Schöning (Ulm) MSC: 03D15 68Q15 PDF BibTeX XML Cite \textit{I. A. Stewart}, Ann. Pure Appl. Logic 66, No. 3, 277--301 (1994; Zbl 0799.03043) Full Text: DOI OpenURL
Okamoto, Tatsuaki; Sakurai, Kouichi; Shizuya, Hiroki How intractable is the discrete logarithm for a general finite group? (English) Zbl 0801.68089 Rueppel, Rainer A. (ed.), Advances in cryptology – EUROCRYPT ’92. Workshop on the theory and applications of cryptographic techniques, Balatonfüred, Hungary, May 24-28, 1992. Proceedings. Berlin: Springer- Verlag. Lect. Notes Comput. Sci. 658, 420-428 (1993). MSC: 68Q25 68W30 68P25 20B40 PDF BibTeX XML Cite \textit{T. Okamoto} et al., Lect. Notes Comput. Sci. 658, 420--428 (1993; Zbl 0801.68089) OpenURL
Gupta, Sanjay On bounded-probability operators and C\(_ =\)P. (English) Zbl 0797.68063 Inf. Process. Lett. 48, No. 2, 93-98 (1993). Reviewer: S.Gupta (Columbus, OH) MSC: 68Q15 03D15 PDF BibTeX XML Cite \textit{S. Gupta}, Inf. Process. Lett. 48, No. 2, 93--98 (1993; Zbl 0797.68063) Full Text: DOI OpenURL
Tarui, Jun Probabilistic polynomials, AC\(^ 0\) functions and the polynomial-time hierarchy. (English) Zbl 0783.68047 Theor. Comput. Sci. 113, No. 1, 167-183 (1993). MSC: 68Q15 PDF BibTeX XML Cite \textit{J. Tarui}, Theor. Comput. Sci. 113, No. 1, 167--183 (1993; Zbl 0783.68047) Full Text: DOI OpenURL
Beigel, Richard; Chang, Richard; Ogiwara, Mitsunori A relationship between difference hierarchies and relativized polynomial hierarchies. (English) Zbl 0776.68043 Math. Syst. Theory 26, No. 3, 293-310 (1993). Reviewer: U.Schöning (Ulm) MSC: 68Q15 PDF BibTeX XML Cite \textit{R. Beigel} et al., Math. Syst. Theory 26, No. 3, 293--310 (1993; Zbl 0776.68043) Full Text: DOI OpenURL
Chang, Richard On the structure of bounded queries to arbitrary NP sets. (English) Zbl 0749.68034 SIAM J. Comput. 21, No. 4, 743-754 (1992). MSC: 68Q15 03D15 03D20 PDF BibTeX XML Cite \textit{R. Chang}, SIAM J. Comput. 21, No. 4, 743--754 (1992; Zbl 0749.68034) Full Text: DOI Link OpenURL
Toda, Seinosuke; Ogiwara, Mitsunori Counting classes are at least as hard as the polynomial-time hierarchy. (English) Zbl 0755.68055 SIAM J. Comput. 21, No. 2, 316-328 (1992). Reviewer: Tao Renji (Beijing) MSC: 68Q15 03D15 PDF BibTeX XML Cite \textit{S. Toda} and \textit{M. Ogiwara}, SIAM J. Comput. 21, No. 2, 316--328 (1992; Zbl 0755.68055) Full Text: DOI Link OpenURL
Fu, Bin Separating \(PH\) from \(PP\) by relativization. (English) Zbl 0793.68077 Acta Math. Sin., New Ser. 8, No. 3, 329-336 (1992). MSC: 68Q25 03D15 68Q15 PDF BibTeX XML Cite \textit{B. Fu}, Acta Math. Sin., New Ser. 8, No. 3, 329--336 (1992; Zbl 0793.68077) Full Text: DOI OpenURL
Sui, Yuefei The polynomially exponential time restrained analytical hierarchy. (English) Zbl 0813.03024 J. Comput. Sci. Technol. 6, No. 3, 282-284 (1991). Reviewer: H.B.Marandjian (Erevan) MSC: 03D15 68Q15 03D10 PDF BibTeX XML Cite \textit{Y. Sui}, J. Comput. Sci. Technol. 6, No. 3, 282--284 (1991; Zbl 0813.03024) Full Text: DOI OpenURL
Torán, Jacobo Complexity classes defined by counting quantifiers. (English) Zbl 0799.68080 J. Assoc. Comput. Mach. 38, No. 3, 753-774 (1991). MSC: 68Q15 PDF BibTeX XML Cite \textit{J. Torán}, J. Assoc. Comput. Mach. 38, No. 3, 753--774 (1991; Zbl 0799.68080) Full Text: DOI OpenURL
Toda, Seinosuke PP is as hard as the polynomial-time hierarchy. (English) Zbl 0733.68034 SIAM J. Comput. 20, No. 5, 865-877 (1991). Reviewer: C.Meinel (Berlin) MSC: 68Q15 03D15 PDF BibTeX XML Cite \textit{S. Toda}, SIAM J. Comput. 20, No. 5, 865--877 (1991; Zbl 0733.68034) Full Text: DOI Link OpenURL
Book, Ronald V. Some observations on separating complexity classes. (English) Zbl 0724.68039 SIAM J. Comput. 20, No. 2, 246-258 (1991). MSC: 68Q15 03D15 PDF BibTeX XML Cite \textit{R. V. Book}, SIAM J. Comput. 20, No. 2, 246--258 (1991; Zbl 0724.68039) Full Text: DOI OpenURL
Toda, Seinosuke On polynomial-time truth-table reduciblity of intractable sets to p- selective sets. (English) Zbl 0722.68059 Math. Syst. Theory 24, No. 2, 69-82 (1991). MSC: 68Q15 PDF BibTeX XML Cite \textit{S. Toda}, Math. Syst. Theory 24, No. 2, 69--82 (1991; Zbl 0722.68059) Full Text: DOI OpenURL
Green, Frederic An oracle separating \(\oplus P\) from \(PP^{PH}\). (English) Zbl 0714.68032 Inf. Process. Lett. 37, No. 3, 149-153 (1991). MSC: 68Q15 03D15 PDF BibTeX XML Cite \textit{F. Green}, Inf. Process. Lett. 37, No. 3, 149--153 (1991; Zbl 0714.68032) Full Text: DOI OpenURL
Li, Hongzhou The polynomial-time hierarchy and oracle set \(A \in \text{PH/poly}\). (English) Zbl 0737.68033 Chin. Sci. Bull. 36, No. 1, 17-20 (1991). MSC: 68Q15 PDF BibTeX XML Cite \textit{H. Li}, Chin. Sci. Bull. 36, No. 1, 17--20 (1991; Zbl 0737.68033) OpenURL
Wagner, Klaus W. Bounded query classes. (English) Zbl 0711.68047 SIAM J. Comput. 19, No. 5, 833-846 (1990). MSC: 68Q15 03D15 PDF BibTeX XML Cite \textit{K. W. Wagner}, SIAM J. Comput. 19, No. 5, 833--846 (1990; Zbl 0711.68047) Full Text: DOI OpenURL
Grädel, Erich Domino games and complexity. (English) Zbl 0711.68044 SIAM J. Comput. 19, No. 5, 787-804 (1990). MSC: 68Q15 03D15 68Q05 91A05 PDF BibTeX XML Cite \textit{E. Grädel}, SIAM J. Comput. 19, No. 5, 787--804 (1990; Zbl 0711.68044) Full Text: DOI OpenURL
Book, Ronald V.; Tang, Shouwen Characterizing polynomial complexity classes by reducibilities. (English) Zbl 0707.68035 Math. Syst. Theory 23, No. 3, 165-174 (1990). MSC: 68Q15 03D15 PDF BibTeX XML Cite \textit{R. V. Book} and \textit{S. Tang}, Math. Syst. Theory 23, No. 3, 165--174 (1990; Zbl 0707.68035) Full Text: DOI OpenURL
Ko, Ker-I Separating and collapsing results on the relativized probabilistic polynomial-time hierarchy. (English) Zbl 0696.68062 J. Assoc. Comput. Mach. 37, No. 2, 415-438 (1990). MSC: 68Q25 03D15 PDF BibTeX XML Cite \textit{K.-I Ko}, J. Assoc. Comput. Mach. 37, No. 2, 415--438 (1990; Zbl 0696.68062) Full Text: DOI OpenURL
Clote, Peter G. A smash-based hierarchy between PTIME and PSPACE. (English) Zbl 0696.03021 Logic and computation, Proc. Workshop, Pittsburgh/PA (USA) 1987, Contemp. Math. 106, 85-100 (1990). Reviewer: R.Murawski MSC: 03D15 03D10 68Q25 68Q05 03F30 PDF BibTeX XML OpenURL
Ferreira, Fernando Stockmeyer induction. (English) Zbl 0769.03032 Feasible mathematics, Proc. Math. Sci. Inst. Workshop, Ithaca/NY (USA) 1989, Prog. Comput. Sci. Appl. Log. 9, 161-180 (1990). Reviewer: F.Ferreira (Lisboa) MSC: 03F30 PDF BibTeX XML Cite \textit{F. Ferreira}, Prog. Comput. Sci. Appl. Log. 9, 161--180 (1990; Zbl 0769.03032) OpenURL
Nasser, Ali Ordnungstheoretisch definierte Zählklassen. (Order theoretic defined counting classes.). (German) Zbl 0734.68040 Jena: Friedrich-Schiller-Universität Jena, Math.-Naturwiss.-Technische Fak., Diss. 63 S. (1989). MSC: 68Q15 68Q05 03D15 03D10 PDF BibTeX XML Cite \textit{A. Nasser}, Ordnungstheoretisch definierte Zählklassen. (Order theoretic defined counting classes.). Jena: Friedrich-Schiller-Universität Jena, Math.-Naturwiss.-Technische Fak. (1989; Zbl 0734.68040) OpenURL
Chen, Zhixiang; Huang, Wenqi K-n-degrees. (Chinese. English summary) Zbl 0695.03021 J., Huazhong (Cent. China) Univ. Sci. Technol. 17, No. 4, 53-57 (1989). MSC: 03D15 03D30 03D55 PDF BibTeX XML OpenURL
Kadin, Jim \(P^{NP[O(\log n)]}\) and sparse turing-complete sets for NP. (English) Zbl 0693.68027 J. Comput. Syst. Sci. 39, No. 3, 282-298 (1989). Reviewer: G.Wechsung MSC: 68Q25 03D15 68Q05 03D10 68Q45 PDF BibTeX XML Cite \textit{J. Kadin}, J. Comput. Syst. Sci. 39, No. 3, 282--298 (1989; Zbl 0693.68027) Full Text: DOI OpenURL
Book, Ronald V.; Tang, Shouwen A note on sparse sets and the polynomial-time hierarchy. (English) Zbl 0688.68029 Inf. Process. Lett. 33, No. 3, 141-143 (1989). Reviewer: J.Vyskoc MSC: 68Q25 PDF BibTeX XML Cite \textit{R. V. Book} and \textit{S. Tang}, Inf. Process. Lett. 33, No. 3, 141--143 (1989; Zbl 0688.68029) Full Text: DOI OpenURL
Torán, Jacobo Succinct representations of counting problems. (English) Zbl 0681.68074 Applied algebra, algebraic algorithms and error-correcting codes, Proc. 6th Int. Conference, AAECC-6, Rome/Italy 1988, Lect. Notes Comput. Sci. 357, 415-426 (1989). MSC: 68Q25 05A99 PDF BibTeX XML OpenURL
Ko, Ker-I Relativized polynomial time hierarchies having exactly k levels. (English) Zbl 0679.68088 SIAM J. Comput. 18, No. 2, 392-408 (1989). MSC: 68Q25 PDF BibTeX XML Cite \textit{K.-I Ko}, SIAM J. Comput. 18, No. 2, 392--408 (1989; Zbl 0679.68088) Full Text: DOI OpenURL
Klapper, Andrew Generalized lowness and highness and probabilistic complexity classes. (English) Zbl 0679.68087 Math. Syst. Theory 22, No. 1, 37-45 (1989). MSC: 68Q25 03D15 PDF BibTeX XML Cite \textit{A. Klapper}, Math. Syst. Theory 22, No. 1, 37--45 (1989; Zbl 0679.68087) Full Text: DOI OpenURL
Bertoni, Alberto; Bruschi, Danilo; Joseph, Deborah; Sitharam, Meera; Young, Paul Generalized Boolean hierarchies and Boolean hierarchies over RP. (English) Zbl 0756.68037 Fundamentals of computation theory, Proc. Int. Conf., FCT ’89, Szeged/Hung. 1989, Lect. Notes Comput. Sci. 380, 35-46 (1989). MSC: 68Q15 PDF BibTeX XML Cite \textit{A. Bertoni} et al., Lect. Notes Comput. Sci. None, 35--46 (1989; Zbl 0756.68037) OpenURL
Kämper, Jürgen Non-uniform proof-systems: A new framework to describe non-uniform and probabilistic complexity classes. (English) Zbl 0666.68047 Foundations of software technology and theoretical computer science, Proc. 8th Conf., Pune/India 1988, Lect. Notes Comput. Sci. 338, 193-210 (1988). MSC: 68Q25 03D15 PDF BibTeX XML OpenURL
Kadin, Jim The polynomial time hierarchy collapses if the Boolean hierarchy collapses. (English) Zbl 0664.03031 SIAM J. Comput. 17, No. 6, 1263-1282 (1988). Reviewer: Tao Renji MSC: 03D15 68Q25 PDF BibTeX XML Cite \textit{J. Kadin}, SIAM J. Comput. 17, No. 6, 1263--1282 (1988; Zbl 0664.03031) Full Text: DOI Link 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
Hartmanis, Juris; Hemachandra, Lane On sparse oracles separating feasible complexity classes. (English) Zbl 0658.68055 Inf. Process. Lett. 28, No. 6, 291-295 (1988). MSC: 68Q25 PDF BibTeX XML Cite \textit{J. Hartmanis} and \textit{L. Hemachandra}, Inf. Process. Lett. 28, No. 6, 291--295 (1988; Zbl 0658.68055) Full Text: DOI Link OpenURL
Pacholski, Leszek Counting and the polynomial-time hierarchy. (English) Zbl 0657.03020 Seminarber., Humboldt-Univ. Berlin, Sekt. Math. 98, 141-150 (1988). MSC: 03D15 03D10 PDF BibTeX XML Cite \textit{L. Pacholski}, Seminarber., Humboldt-Univ. Berlin, Sekt. Math. 98, 141--150 (1988; Zbl 0657.03020) OpenURL
Book, R.; Orponen, P.; Russo, D.; Watanabe, O. Lowness properties of sets in the exponential-time hierarchy. (English) Zbl 0652.68059 SIAM J. Comput. 17, No. 3, 504-516 (1988). MSC: 68Q25 03D15 PDF BibTeX XML Cite \textit{R. Book} et al., SIAM J. Comput. 17, No. 3, 504--516 (1988; Zbl 0652.68059) Full Text: DOI 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
Amir, Amihood; Gasarch, William I. Polynomial terse sets. (English) Zbl 0646.68049 Inf. Comput. 77, No. 1, 37-56 (1988). MSC: 68Q25 PDF BibTeX XML Cite \textit{A. Amir} and \textit{W. I. Gasarch}, Inf. Comput. 77, No. 1, 37--56 (1988; Zbl 0646.68049) Full Text: DOI OpenURL
Balcázar, José Luis; Díaz, Josep; Gabarró, Joaquim Structural complexity. I. (English) Zbl 0638.68040 EATCS Monographs on Theoretical Computer Science, Vol. 11. Berlin etc.: Springer-Verlag. IX, 191 p., DM 54.00 (1988). Reviewer: U.Schöning MSC: 68Q05 68Q25 03D15 03D10 68-02 03-02 PDF BibTeX XML Cite \textit{J. L. Balcázar} et al., Structural complexity. I. Berlin etc.: Springer-Verlag (1988; Zbl 0638.68040) OpenURL
Takeuti, Gaisi Computational complexity and proof theory. (English. Japanese original) Zbl 0681.03039 Sugaku Expo. 1, No. 1, 1-14 (1988); translation from Sûgaku 39, No. 2, 110-123 (1987). MSC: 03F05 03F25 68Q25 03D15 PDF BibTeX XML Cite \textit{G. Takeuti}, Sugaku Expo. 1, No. 1, 1--14 (1987; Zbl 0681.03039); translation from Sûgaku 39, No. 2, 110--123 (1987) OpenURL
Hartmanis, J. Structural complexity column - Sparse complete sets of NP and the optimal collapse of the polynomial hierarchy. (English) Zbl 0661.68046 Bull. EATCS 32, 73-81 (1987). Reviewer: U.Schöning MSC: 68Q25 68Q05 03D15 PDF BibTeX XML Cite \textit{J. Hartmanis}, Bull. EATCS 32, 73--81 (1987; Zbl 0661.68046) OpenURL
Babai, László Random oracles separate PSPACE from the polynomial-time hierarchy. (English) Zbl 0654.68052 Inf. Process. Lett. 26, 51-53 (1987). MSC: 68Q25 94C10 03D15 PDF BibTeX XML Cite \textit{L. Babai}, Inf. Process. Lett. 26, 51--53 (1987; Zbl 0654.68052) Full Text: DOI OpenURL
Boppana, Ravi B.; Håstad, Johan; Zachos, Stathis Does co-NP have short interactive proofs ? (English) Zbl 0653.68037 Inf. Process. Lett. 25, 127-132 (1987). MSC: 68Q25 03D15 PDF BibTeX XML Cite \textit{R. B. Boppana} et al., Inf. Process. Lett. 25, 127--132 (1987; Zbl 0653.68037) Full Text: DOI OpenURL
Wagner, Klaus W. More complicated questions about maxima and minima, and some closures of NP. (English) Zbl 0653.03027 Theor. Comput. Sci. 51, 53-80 (1987). MSC: 03D15 68Q25 PDF BibTeX XML Cite \textit{K. W. Wagner}, Theor. Comput. Sci. 51, 53--80 (1987; Zbl 0653.03027) Full Text: DOI OpenURL
Takeuti, Gaisi Computational complexity and proof theory. (Japanese) Zbl 0646.03052 Sûgaku 39, No. 2, 110-123 (1987). Reviewer: M.Yasuhara MSC: 03F05 03F25 68Q25 03D15 PDF BibTeX XML Cite \textit{G. Takeuti}, Sūgaku 39, No. 2, 110--123 (1987; Zbl 0646.03052) OpenURL
Book, Ronald V. (ed.) Studies in complexity theory. (English) Zbl 0666.68049 Research Notes in Theoretical Computr Science. London etc.: Pitman Publishing; VIII, 226 p.; £17.95 (1986). MSC: 68Q25 03D15 03H15 PDF BibTeX XML OpenURL
Buss, S. R. The polynomial hierarchy and intuitionistic bounded arithmetic. (English) Zbl 0654.03043 Structure in complexity theory, Proc. Conf., Berkeley/Calif. 1986, Lect. Notes Comput. Sci. 223, 77-103 (1986). Reviewer: P.Clote MSC: 03F30 03F10 03D15 PDF BibTeX XML OpenURL
Wagner, Klaus W. Some observations on the connection between counting and recursion. (English) Zbl 0637.03034 Theor. Comput. Sci. 47, 131-147 (1986). Reviewer: G.B.Marandzjan MSC: 03D15 PDF BibTeX XML Cite \textit{K. W. Wagner}, Theor. Comput. Sci. 47, 131--147 (1986; Zbl 0637.03034) Full Text: DOI OpenURL
Gundermann, Thomas; Wechsung, Gerd Nondeterministic Turing machines with modified acceptance. (English) Zbl 0628.03026 Mathematical foundations of computer science, Proc. 12th Symp., Bratislava/Czech. 1986, Lect. Notes Comput. Sci. 233, 396-404 (1986). Reviewer: E.Heinrich MSC: 03D15 03D10 68Q05 68Q25 PDF BibTeX XML OpenURL
Balcázar, Jose L.; Book, Ronald V.; Schöning, Uwe The polynomial-time hierarchy and sparse oracles. (English) Zbl 0625.68033 J. Assoc. Comput. Mach. 33, No. 3, 603-617 (1986). MSC: 68Q25 PDF BibTeX XML Cite \textit{J. L. Balcázar} et al., J. Assoc. Comput. Mach. 33, 603--617 (1986; Zbl 0625.68033) Full Text: DOI OpenURL
Balćzar, José L.; Book, Ronald V.; Schöning, Uwe Sparse sets, lowness and highness. (English) Zbl 0621.68033 SIAM J. Comput. 15, 739-747 (1986). MSC: 68Q25 68Q05 03D15 PDF BibTeX XML Cite \textit{J. L. Balćzar} et al., SIAM J. Comput. 15, 739--747 (1986; Zbl 0621.68033) Full Text: DOI Link OpenURL
Huynh, Dung T. A simple proof for the \(\Sigma ^ p_ 2\) upper bound of the inequivalence problem for semilinear sets. (English) Zbl 0617.68050 Elektron. Informationsverarbeitung Kybernetik 22, 147-156 (1986). Reviewer: H.Alt MSC: 68Q25 68Q45 68Q05 03D15 03D20 PDF BibTeX XML Cite \textit{D. T. Huynh}, Elektron. Informationsverarbeitung Kybernetik 22, 147--156 (1986; Zbl 0617.68050) OpenURL
Immerman, Neil Relational queries computable in polynomial time. (English) Zbl 0612.68086 Inf. Control 68, 86-104 (1986). MSC: 68P20 03C13 PDF BibTeX XML Cite \textit{N. Immerman}, Inf. Control 68, 86--104 (1986; Zbl 0612.68086) Full Text: DOI OpenURL
Homer, Steve; Reif, John Arithmetic theories for computational complexity problems. (English) Zbl 0611.03018 Inf. Control 69, 1-11 (1986). Reviewer: E.Heinrich MSC: 03D15 68Q25 PDF BibTeX XML Cite \textit{S. Homer} and \textit{J. Reif}, Inf. Control 69, 1--11 (1986; Zbl 0611.03018) Full Text: DOI OpenURL