{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T19:30:32Z","timestamp":1787340632480,"version":"build-2736575974"},"reference-count":21,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"1","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Comput."],"published-print":{"date-parts":[[1985,2]]},"abstract":"<jats:p>Let A be a set having polynomial size circuits. If A is also known to be in NP, then we may conclude that the graph of the polynomial size circuits for A is actually in $\\Pi _2^p $. Using this observation, we show that sets in NP which have polynomial size ciruits are in $L_3^p $, the third level of the low hierarchy in NP. By a similar technique, we are able to show that some other intuitively low sets in NP are in $L_2^p $, and even in a certain refinement of $L_2^p $. As a consequence, sparse sets are not strong nondeterministic polynomial time Turing complete in NP unless the polynomial time hierarchy collapses to $\\Delta _2^p $.<\/jats:p>","DOI":"10.1137\/0214003","type":"journal-article","created":{"date-parts":[[2005,2,24]],"date-time":"2005-02-24T06:25:35Z","timestamp":1109226335000},"page":"41-51","source":"Crossref","is-referenced-by-count":68,"title":["On Circuit-Size Complexity and the Low Hierarchy in NP"],"prefix":"10.1137","volume":"14","author":[{"given":"Ker-I","family":"Ko","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Uwe","family":"Sch\u00f6ning","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2006,7,13]]},"reference":[{"key":"R1","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.1978.37"},{"key":"R2","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(78)90007-5"},{"key":"R3","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-09118-1_8"},{"key":"R4","doi-asserted-by":"publisher","DOI":"10.1137\/0206023"},{"key":"R5","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-08860-1_6"},{"key":"R6","doi-asserted-by":"publisher","DOI":"10.1016\/S0019-9958(74)90473-2"},{"key":"R7","doi-asserted-by":"publisher","DOI":"10.1137\/0208034"},{"key":"R8","doi-asserted-by":"crossref","unstructured":"J. Hartmanis, V. Sewelson, N. Immerman,  Sparse sets in  NP\u2212P: EXPTIME versus NEXPTIME,  Proc. 15th ACM Symposium on Theory of Computing,  1983,  382\u2013391","DOI":"10.1145\/800061.808769"},{"key":"R9","doi-asserted-by":"crossref","unstructured":"R. Karp, R. Lipton,  Some connections between nonuniform and uniform complexity classes,  Proc. 12th ACM Symposium on Theory of Computing,  1980,  302\u2013309","DOI":"10.1145\/800141.804678"},{"key":"R10","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(83)90013-2"},{"key":"R11","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(75)90016-X"},{"key":"R12","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(82)90050-2"},{"key":"R13","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(82)90085-8"},{"key":"R14","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(82)90002-2"},{"key":"R15","unstructured":"A. R. Meyer, M. S. Paterson,  With what frequency are apparently intractable problems difficult? MIT\/LCS\/TM-126, Lab for Computer Science, Massachusetts Institute of Technology, Cambridge,  1979"},{"key":"R16","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(83)90027-2"},{"key":"R17","unstructured":"U. Sch\u00f6ning,  On sparse and strong nondeterministic Turing complete sets in NP, unpublished manuscript"},{"key":"R18","doi-asserted-by":"publisher","DOI":"10.1007\/BF01744288"},{"key":"R19","doi-asserted-by":"publisher","DOI":"10.2307\/2271876"},{"key":"R20","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(76)90061-X"},{"key":"R21","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(76)90097-1"}],"container-title":["SIAM Journal on Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/0214003","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T18:42:08Z","timestamp":1787337728000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/0214003"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1985,2]]},"references-count":21,"journal-issue":{"issue":"1","published-print":{"date-parts":[[1985,2]]}},"alternative-id":["10.1137\/0214003"],"URL":"https:\/\/doi.org\/10.1137\/0214003","relation":{},"ISSN":["0097-5397","1095-7111"],"issn-type":[{"value":"0097-5397","type":"print"},{"value":"1095-7111","type":"electronic"}],"subject":[],"published":{"date-parts":[[1985,2]]}}}