{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,1,30]],"date-time":"2024-01-30T21:10:01Z","timestamp":1706649001385},"reference-count":21,"publisher":"Duke University Press","issue":"2","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Notre Dame J. Formal Logic"],"published-print":{"date-parts":[[2000,4,1]]},"DOI":"10.1305\/ndjfl\/1038234608","type":"journal-article","created":{"date-parts":[[2003,2,25]],"date-time":"2003-02-25T20:23:23Z","timestamp":1046204603000},"source":"Crossref","is-referenced-by-count":5,"title":["Complexity of the $r$-query Tautologies in the Presence of a Generic Oracle"],"prefix":"10.1215","volume":"41","author":[{"given":"Toshio","family":"Suzuki","sequence":"first","affiliation":[]}],"member":"73","reference":[{"key":"1","doi-asserted-by":"crossref","unstructured":"Ambos-Spies, K., H. Fleischhack, and H. Hagen, \"$p$-generic sets\", pp. 58\u201368 in <i>Automata, L<\/i>anguages and Programming (Antwerp, 1984), edited by J. Paredaens, Springer-Verlag, Berlin, 1984.","DOI":"10.1007\/3-540-13345-3_5"},{"key":"2","doi-asserted-by":"publisher","unstructured":"Baker, T., J. Gill, and R. Solovay, \"Relativizations of the $\\mathcal{P}=$?$\\mathcal{N\\!P}$ question\", <i>SIAM Journal on Computing<\/i>, vol. 4 (1975), pp. 431\u201342.","DOI":"10.1137\/0204037"},{"key":"3","doi-asserted-by":"crossref","unstructured":"Balc\u00e1zar, J. L., R. V. Book, and U. Sch \u00f6ning, \"On bounded query machines\", <i>Theoretical Computer Science<\/i>, vol. 40 (1985), pp. 237\u201343.","DOI":"10.1016\/0304-3975(85)90168-9"},{"key":"4","unstructured":"Balc\u00e1zar, J. L., J. D\u00edaz, and J. Gabarr\u00f3, <i>Structural C<\/i>omplexity. I, Springer-Verlag, Berlin, 2d edition, 1995."},{"key":"5","doi-asserted-by":"publisher","unstructured":"Bennett, C. H., and J. Gill, \"Relative to a random oracle ${A}$, <b>P<\/b>$^{A}\\not=$ <b>NP<\/b>$^{A}\\not=$ co-<b>NP<\/b>$^{A}$ with probability $1$\", <i>SIAM Journal on Computing<\/i>, vol. 10 (1981), pp. 96\u2013113.","DOI":"10.1137\/0210008"},{"key":"6","doi-asserted-by":"crossref","unstructured":"Blum, M., and R. Impagliazzo, \"Generic oracles and oracle classes\", pp. 118\u201326 in <i>28th A<\/i>nnual Symposium on Foundations of Computer Science, IEEE Computer Society Press, Los Alamitos, 1987.","DOI":"10.1109\/SFCS.1987.30"},{"key":"7","doi-asserted-by":"publisher","unstructured":"Book, R. V., \"Bounded query machines: on N\"P and PSPACE, <i>Theoretical Computer Science<\/i>, vol. 15 (1981), pp. 27\u201339.","DOI":"10.1016\/0304-3975(81)90061-X"},{"key":"8","doi-asserted-by":"publisher","unstructured":"Cohen, P., \"The independence of the continuum hypothesis\", <i>Proceedings of the National Academy of the Sciences of the United States of America<\/i>, vol. 50 (1963), pp. 1143\u201348.","DOI":"10.1073\/pnas.50.6.1143"},{"key":"9","doi-asserted-by":"publisher","unstructured":"Cohen, P. J., \"The independence of the continuum hypothesis. I\"I, <i>Proceedings of the National Academy of the Sciences of the United States of America<\/i>, vol. 51 (1964), pp. 105\u201310.","DOI":"10.1073\/pnas.51.1.105"},{"key":"10","unstructured":"Dowd, M., \"Forcing and the ${P}$-hierarchy\", Technical Report LCSR-TR-35, Rutgers University, New Brunswick, 1982."},{"key":"11","doi-asserted-by":"publisher","unstructured":"Dowd, M., \"Generic oracles, uniform machines, and codes\", <i>Information and Computation<\/i>, vol. 96 (1992), pp. 65\u201376.","DOI":"10.1016\/0890-5401(92)90055-K"},{"key":"12","doi-asserted-by":"publisher","unstructured":"Feferman, S., \"Some applications of the notions of forcing and generic sets\", <i>Fundamenta Mathematicae<\/i>, vol. 56 (1964\/1965), pp. 325\u201345.","DOI":"10.4064\/fm-56-3-325-345"},{"key":"13","doi-asserted-by":"publisher","unstructured":"Hinman, P. G., \"Some applications of forcing to hierarchy problems in arithmetic\", <i>Zeitschrift f\u00fcr mathematische Logik und Grundlagen der Mathematik<\/i>, vol. 15 (1969), pp. 341\u201352.","DOI":"10.1002\/malq.19690152004"},{"key":"14","doi-asserted-by":"crossref","unstructured":"Jockusch, C. G., Jr., \"Degrees of generic sets\", pp. 110\u201339 in <i>Recursion T<\/i>heory: Its Generalisation and Applications (Proceedings of the Logic Colloquium, Leeds, 1979), edited by F. R. Drake and S. S. Wainer, Cambridge University Press, Cambridge, 1980.","DOI":"10.1017\/CBO9780511629181.004"},{"key":"15","unstructured":"Kunen, K., <i>Set T<\/i>heory. An Introduction to Independence Proofs, North-Holland, Amsterdam, 1980."},{"key":"16","doi-asserted-by":"crossref","unstructured":"Mehlhorn, K., \"On the size of sets of computable functions\", pp. 190\u201396 in <i>14th A<\/i>nnual IEEE Symposium on Switching and Automata Theory, IEEE Computer Society, Northridge, 1973.","DOI":"10.1109\/SWAT.1973.23"},{"key":"17","doi-asserted-by":"publisher","unstructured":"Odifreddi, P., \"Forcing and reducibilities\", <i>The Journal of Symbolic Logic<\/i>, vol. 48 (1983), pp. 288\u2013310.","DOI":"10.2307\/2273547"},{"key":"18","doi-asserted-by":"publisher","unstructured":"Poizat, B., \"$\\mathcal{Q}=\\mathcal{N\\!Q}$?\", <i>The Journal of Symbolic Logic<\/i>, vol. 51 (1986), pp. 22\u201332.","DOI":"10.2307\/2273938"},{"key":"19","unstructured":"Rogers, H., Jr., <i>Theory of R<\/i>ecursive Functions and Effective Computability, McGraw-Hill, New York, 1967."},{"key":"20","unstructured":"Suzuki, T., \"Recognizing tautology by a deterministic algorithm whose while-loop's execution time is bounded by forcing\", <i>Kobe Journal of Mathematics<\/i>, vol. 15 (1998), pp. 91\u2013102."},{"key":"21","doi-asserted-by":"publisher","unstructured":"Tanaka, H., and M. Kudoh, \"On relativized probabilistic polynomial time algorithms\", <i>Journal of the Mathematical Society of Japan<\/i>, vol. 49 (1997), pp. 15\u201330.","DOI":"10.2969\/jmsj\/04910015"}],"container-title":["Notre Dame Journal of Formal Logic"],"original-title":[],"link":[{"URL":"https:\/\/projecteuclid.org\/journalArticle\/Download?urlid=10.1305\/ndjfl\/1038234608","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,1,30]],"date-time":"2024-01-30T20:55:37Z","timestamp":1706648137000},"score":1,"resource":{"primary":{"URL":"https:\/\/projecteuclid.org\/journals\/notre-dame-journal-of-formal-logic\/volume-41\/issue-2\/Complexity-of-the-r-query-Tautologies-in-the-Presence-of\/10.1305\/ndjfl\/1038234608.full"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2000,4,1]]},"references-count":21,"journal-issue":{"issue":"2","published-online":{"date-parts":[[2000,4,1]]}},"URL":"https:\/\/doi.org\/10.1305\/ndjfl\/1038234608","relation":{},"ISSN":["0029-4527"],"issn-type":[{"value":"0029-4527","type":"print"}],"subject":[],"published":{"date-parts":[[2000,4,1]]}}}