{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2023,9,13]],"date-time":"2023-09-13T19:19:32Z","timestamp":1694632772144},"reference-count":24,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[2008,5,28]],"date-time":"2008-05-28T00:00:00Z","timestamp":1211932800000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Arch. Math. Logic"],"published-print":{"date-parts":[[2008,7]]},"DOI":"10.1007\/s00153-008-0076-4","type":"journal-article","created":{"date-parts":[[2008,5,27]],"date-time":"2008-05-27T09:37:43Z","timestamp":1211881063000},"page":"159-180","source":"Crossref","is-referenced-by-count":1,"title":["Does truth-table of linear norm reduce the one-query tautologies to a random oracle?"],"prefix":"10.1007","volume":"47","author":[{"given":"Masahiro","family":"Kumabe","sequence":"first","affiliation":[]},{"given":"Toshio","family":"Suzuki","sequence":"additional","affiliation":[]},{"given":"Takeshi","family":"Yamazaki","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2008,5,28]]},"reference":[{"key":"76_CR1","doi-asserted-by":"crossref","first-page":"2","DOI":"10.1016\/j.apal.2005.06.003","volume":"138","author":"E. Allender","year":"2006","unstructured":"Allender E., Buhrman H., Kouck\u00fd M.: What can be effectively reduced to the Kolmogorov-random strings?. Ann. Pure Appl. Logic 138, 2\u201319 (2006)","journal-title":"Ann. Pure Appl. Logic"},{"key":"76_CR2","doi-asserted-by":"crossref","first-page":"23","DOI":"10.1007\/3-540-16486-3_87","volume-title":"Structure in Complexity Theory. Lecture Notes in Computer Sciences, vol. 223","author":"K. Ambos-Spies","year":"1986","unstructured":"Ambos-Spies K.: Randomness, relativizations, and polynomial reducibilities. In: Selman, A.L. (eds) Structure in Complexity Theory. Lecture Notes in Computer Sciences, vol. 223, pp. 23\u201334. Springer, Berlin (1986)"},{"key":"76_CR3","doi-asserted-by":"crossref","first-page":"177","DOI":"10.1016\/0304-3975(87)90053-3","volume":"51","author":"K. Ambos-Spies","year":"1987","unstructured":"Ambos-Spies K., Fleischhack H., Huwig H.: Diagonalizations over polynomial time computable sets. Theor. Comput. Sci. 51, 177\u2013204 (1987)","journal-title":"Theor. Comput. Sci."},{"key":"76_CR4","first-page":"1","volume-title":"Complexity, Logic, and Recursion Theory. Lecture Notes in Pure and Applied Mathematics, vol. 187","author":"K. Ambos-Spies","year":"1997","unstructured":"Ambos-Spies K., Mayordomo E.: Resource-bounded measure and randomness. In: Sorbi, A. (eds) Complexity, Logic, and Recursion Theory. Lecture Notes in Pure and Applied Mathematics, vol. 187, pp. 1\u201347. Marcel Dekker, New York (1997)"},{"key":"76_CR5","doi-asserted-by":"crossref","first-page":"3","DOI":"10.1016\/0304-3975(96)89424-2","volume":"168","author":"K. Ambos-Spies","year":"1996","unstructured":"Ambos-Spies K., Neis H., Terwijin S.A.: Genericity and measure for exponential time. Theor. Comput. Sci. 168, 3\u201319 (1996)","journal-title":"Theor. Comput. Sci."},{"key":"76_CR6","doi-asserted-by":"crossref","DOI":"10.1007\/978-3-642-97062-7","volume-title":"Structural Complexity I","author":"J.L. Balc\u00e1zar","year":"1988","unstructured":"Balc\u00e1zar J.L., D\u00edaz J., Gabarr\u00f3 J.: Structural Complexity I. Springer, Berlin (1988)"},{"key":"76_CR7","doi-asserted-by":"crossref","first-page":"96","DOI":"10.1137\/0210008","volume":"10","author":"C.H. Bennett","year":"1981","unstructured":"Bennett C.H., Gill J.: Relative to a random oracle A, P A \u2260\u00a0NP A \u2260\u00a0co NP A with probability 1. SIAM J. Comput. 10, 96\u2013113 (1981)","journal-title":"SIAM J. Comput."},{"key":"76_CR8","doi-asserted-by":"crossref","first-page":"65","DOI":"10.1016\/0890-5401(92)90055-K","volume":"96","author":"M. Dowd","year":"1992","unstructured":"Dowd M.: Generic oracles, uniform machines, and codes. Inf. Comput. 96, 65\u201376 (1992)","journal-title":"Inf. Comput."},{"key":"76_CR9","doi-asserted-by":"crossref","first-page":"411","DOI":"10.2178\/bsl\/1154698741","volume":"12","author":"R. Downey","year":"2006","unstructured":"Downey R., Hirschfeldt D.R., Nies A., Terwijn S.A.: Calibrating randomness. Bull. Symb. Log. 12, 411\u2013491 (2006)","journal-title":"Bull. Symb. Log."},{"key":"76_CR10","unstructured":"Jockusch, C.G.: Reducibilities in recursive function theory, Ph.D. thesis, MIT Press, Cambridge (1966)"},{"key":"76_CR11","doi-asserted-by":"crossref","first-page":"39","DOI":"10.1016\/0020-0190(82)90139-9","volume":"14","author":"K.-I. Ko","year":"1982","unstructured":"Ko K.-I.: Some observations on the probabilistic algorithms and NP-hard problems. Inform. Process. Lett. 14, 39\u201343 (1982)","journal-title":"Inform. Process. Lett."},{"key":"76_CR12","unstructured":"Kumabe, M., Suzuki, T., Yamazaki, T.: Logarithmic truth-table reductions and minimum sizes of forcing conditions (preliminary draft). In: Proof Theory and Computation Theory, Kyoto, 2005, S\u016brikaisekikenkyusho K\u014dkyuroku, no. 1442, pp. 42\u201347 (2005)"},{"key":"76_CR13","unstructured":"Kumabe, M., Suzuki, T., Yamazaki, T., Kumabe, M., Suzuki, T., Yamazaki, T.: Truth-table reductions and minimum sizes of forcing conditions (preliminary draft). In: S\u016brikaisekikenkyusho K\u014dkyuroku, no. 1533, pp. 9\u201314 (2007)"},{"key":"76_CR14","doi-asserted-by":"crossref","first-page":"103","DOI":"10.1016\/0304-3975(75)90016-X","volume":"1","author":"R.E. Ladner","year":"1975","unstructured":"Ladner R.E., Lynch N.A., Selman A.L.: A comparison of polynomial time reducibilities. Theor. Comput. Sci. 1, 103\u2013123 (1975)","journal-title":"Theor. Comput. Sci."},{"key":"76_CR15","doi-asserted-by":"crossref","first-page":"284","DOI":"10.1090\/S0002-9904-1944-08111-1","volume":"50","author":"E.L. Post","year":"1944","unstructured":"Post E.L.: Recursively enumerable sets of positive integers and their decision problems. Bull. Am. Math. Soc. 50, 284\u2013316 (1944)","journal-title":"Bull. Am. Math. Soc."},{"key":"76_CR16","unstructured":"Rogers, H. Jr.: Theory of recursive functions and effective computability. Massachusetts Institute of Technology (1987) (Original edition: MacGraw-Hill, New York, 1967)"},{"key":"76_CR17","volume-title":"Degrees of Unsolvability, Annals of Mathematics Studies, vol. 55","author":"G.E. Sacks","year":"1963","unstructured":"Sacks G.E.: Degrees of Unsolvability, Annals of Mathematics Studies, vol. 55. Princeton university press, Princeton (1963)"},{"key":"76_CR18","first-page":"91","volume":"15","author":"T. Suzuki","year":"1998","unstructured":"Suzuki T.: Recognizing tautology by a deterministic algorithm whose while-loop\u2019s execution time is bounded by forcing. Kobe J. Math. 15, 91\u2013102 (1998)","journal-title":"Kobe J. Math."},{"key":"76_CR19","unstructured":"Suzuki, T.: Computational complexity of Boolean formulas with query symbols. Doctoral dissertation, Institute of Mathematics, University of Tsukuba, Tsukuba-City, Japan (1999)"},{"key":"76_CR20","doi-asserted-by":"crossref","first-page":"142","DOI":"10.1305\/ndjfl\/1038234608","volume":"41","author":"T. Suzuki","year":"2000","unstructured":"Suzuki T.: Complexity of the r-query tautologies in the presence of a generic oracle. Notre Dame J. Formal Logic 41, 142\u2013151 (2000)","journal-title":"Notre Dame J. Formal Logic"},{"key":"76_CR21","doi-asserted-by":"crossref","first-page":"117","DOI":"10.1305\/ndjfl\/1054837938","volume":"42","author":"T. Suzuki","year":"2001","unstructured":"Suzuki T.: Forcing complexity: minimum sizes of forcing conditions. Notre Dame J. Formal Logic 42, 117\u2013120 (2001)","journal-title":"Notre Dame J. Formal Logic"},{"key":"76_CR22","doi-asserted-by":"crossref","first-page":"66","DOI":"10.1006\/inco.2002.3149","volume":"176","author":"T. Suzuki","year":"2002","unstructured":"Suzuki T.: Degrees of Dowd-type generic oracles. Inf. Comput. 176, 66\u201387 (2002)","journal-title":"Inf. Comput."},{"key":"76_CR23","doi-asserted-by":"crossref","first-page":"751","DOI":"10.1007\/s00153-005-0283-1","volume":"44","author":"T. Suzuki","year":"2005","unstructured":"Suzuki T.: Bounded truth table does not reduce the one-query tautologies to a random oracle. Arch. Math. Logic 44, 751\u2013762 (2005)","journal-title":"Arch. Math. Logic"},{"key":"76_CR24","doi-asserted-by":"crossref","first-page":"35","DOI":"10.1016\/0304-3975(91)90314-R","volume":"81","author":"S. Tang","year":"1991","unstructured":"Tang S., Book R.V.: Polynomial-time reducibilities and \u201calmost all\u201d oracle sets. Theor. Comput. Sci. 81, 35\u201347 (1991)","journal-title":"Theor. Comput. Sci."}],"container-title":["Archive for Mathematical Logic"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00153-008-0076-4.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00153-008-0076-4\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00153-008-0076-4","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,9,11]],"date-time":"2021-09-11T05:32:35Z","timestamp":1631338355000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00153-008-0076-4"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2008,5,28]]},"references-count":24,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2008,7]]}},"alternative-id":["76"],"URL":"https:\/\/doi.org\/10.1007\/s00153-008-0076-4","relation":{},"ISSN":["0933-5846","1432-0665"],"issn-type":[{"value":"0933-5846","type":"print"},{"value":"1432-0665","type":"electronic"}],"subject":[],"published":{"date-parts":[[2008,5,28]]}}}