 | Timo Lepistö, Arto Salomaa - Computers - 1988 - 762 pages
...[HIS] Beigel, R. "Bounded Queries to SAT and the Boolean Hierarchy", manuscript, June 1987. Baker, T., J. Gill, and R. Solovay. "Relativizations of the P =? NP Question", SIAM Journal on Computing, 4(4):431-442, December 1975. Berman, L. and J. Hartmanis. "On Isomorphisms and Density of NP and Other... | |
 | Grzegorz Rozenberg, Arto Salomaa - Computers - 1993 - 642 pages
...poly-logarithmic time. In Proceedings of the 2!Fd ACM Symposium on Theory of Computing, pages 21-31, 1991. [BGS75] T. Baker, J. Gill, and R. Solovay. Relativizations...of the P =? NP question. SIAM Journal on Computing, 4(4):431-442, December 1975. [BLS84] RV Book, TJ Long, and AL Selman. Quantitative relativizations... | |
 | Ding-Zhu Du, Xiang-Sun Zhang - Computers - 1994 - 708 pages
...oracle, pA ¿ NPA ¿ co¿NP'¿ with probability one. SIAM Journal on Computing, 10:96—113, 1981. [BGS75] T. Baker, J. Gill, and R. Solovay. Relativizations...of the P = NP question. SIAM Journal on Computing, 4(4):431—442, 1975. [BI87J M. Blum and R. Impagliazzo. Generic oracles and oracle classes. In Proceedings... | |
 | Lane A. Hemaspaandra, Alan L. Selman - Computers - 1997 - 360 pages
...Counting classes: Thresholds, parity, mods, and fewness. Theoretical Computer Science, 103:3-23, 1992. [BGS75] T. Baker, J. Gill, and R. Solovay. Relativizations...of the P - NP question. SIAM Journal on Computing, 4(4):431-442, 1975. [BM88] L. Babai and S. Moran. Arthur-Merlin games: a randomized proof system, and... | |
 | Jürgen Dix, Ulrich Furbach, Anil Nerode - Computers - 1997 - 474 pages
...practical importance in a hardware implementation of their scheme and warrant further study. References 1. T. Baker, J. Gill, and R. Solovay . "Relativizations of the P =? NP question ". SIAM Journal of Computing. , 1993. 431-442. 2. M. Cadoli and M. Schaerf. 'A survey on complexity results for non-monotonic... | |
 | Lubos Brim, Jiri Zlatuska, Josef Gruska - Computers - 1998 - 876 pages
...and measure for exponential time. Theoretical Computer Science 168 (1996) 3-19. 6. T. Baker, J. Gill, R. Solovay. Relativizations of the P =?NP question. SIAM Journal on Computing 5 (1975) 431-442. 7. C. Bennett, J. Gill. Relative to a random oracle pA ¿ NPA ¿ co-NP'¿ with probability... | |
 | Allen Kent, James G. Williams - Computers - 1999 - 408 pages
...(1978). 20. L. Stockmeyer, "The Polynomial-Time Hierarchy," Theoret. Comput. Sci., 3, 1-22 (1977). 21. T. Baker, J. Gill, and R. Solovay, "Relativizations of the P = NP Question," SIAM J. Comput., 4, 431-442(1975). 22. K. Ko, "Relativized Polynomial Time Hierarchies Having Exactly k... | |
 | Peter Bürgisser - Mathematics - 2000 - 192 pages
...J.-L. Lions, editors, Handbook of Numerical Analysis, volume V, pages 3-207. North-Holland, 1997. [3] T. Baker, J. Gill, and R. Solovay. Relativizations of the P =?NP question. SIAM J. Comp., 4:431-442, 1975. [4] JL Balcazar, J. Diaz, and J. Gabarro. Structural Complexity I. Springer... | |
 | James A. Carlson, Arthur Jaffe, Andrew Wiles, Clay Mathematics Institute, American Mathematical Society - Mathematics - 2006 - 192 pages
...RB Boppana, The monotone circuit complexity of boolean functions, Combinatorica 7 (1987), 1-22. [3] T. Baker, J. Gill, and R. Solovay, Relativizations of the P =? NP question, SICOMP: SIAM Journal on Computing, 1975. [4] L. Blum, F. Cucker, M. Shub, and S. Smale, Complexity... | |
| |
T. Baker, J. Gill, and R. Solovay. Relativizations of the P = NP question. 