{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2023,10,10]],"date-time":"2023-10-10T06:13:25Z","timestamp":1696918405897},"reference-count":26,"publisher":"Wiley","issue":"3","license":[{"start":{"date-parts":[[2006,11,13]],"date-time":"2006-11-13T00:00:00Z","timestamp":1163376000000},"content-version":"vor","delay-in-days":3603,"URL":"http:\/\/onlinelibrary.wiley.com\/termsAndConditions#vor"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Mathematical Logic Qtrly"],"published-print":{"date-parts":[[1997,1]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>Enumeration reducibility is a notion of relative computability between sets of natural numbers where only positive information about the sets is used or produced. Extending e\u2010reducibility to partial functions characterises relative computability between partial functions. We define a polynomial time enumeration reducibility that retains the character of enumeration reducibility and show that it is equivalent to conjunctive non\u2010deterministic polynomial time reducibility. We define the polynomial time <jats:italic>e<\/jats:italic>\u2010degrees as the equivalence classes under this reducibility and investigate their structure on the recursive sets, showing in particular that the pe\u2010degrees of the computable sets are dense and do not form a lattice, but that minimal pairs exist. We define a jump operator and use it to produce a characterisation of the polynomial hierarchy.<\/jats:p>","DOI":"10.1002\/malq.19970430302","type":"journal-article","created":{"date-parts":[[2007,5,30]],"date-time":"2007-05-30T07:23:59Z","timestamp":1180509839000},"page":"287-310","source":"Crossref","is-referenced-by-count":2,"title":["On Nondeterminism, Enumeration Reducibility and Polynomial Bounds"],"prefix":"10.1002","volume":"43","author":[{"given":"Kate","family":"Copestake","sequence":"first","affiliation":[]}],"member":"311","published-online":{"date-parts":[[2006,11,13]]},"reference":[{"key":"e_1_2_1_2_2","volume-title":"Polynomial Time Degrees. Current Trends in Theoretical Computer Science","author":"Ambos\u2010Spies K.","year":"1987"},{"key":"e_1_2_1_3_2","volume-title":"Structural Complexity I. EATCS Monographs on Theoretical Computer Science 11","author":"Balc\u00e1zar J. L.","year":"1988"},{"key":"e_1_2_1_4_2","doi-asserted-by":"crossref","unstructured":"Cook S. A. The complexity of theorem proving procedures. Proceedings Third Annual ACM Symposium on the Theory of Computing1971 151\u2013158.","DOI":"10.1145\/800157.805047"},{"key":"e_1_2_1_5_2","doi-asserted-by":"publisher","DOI":"10.2307\/2273104"},{"key":"e_1_2_1_6_2","unstructured":"Cooper S. B. The enumeration degrees are not dense. To appear."},{"key":"e_1_2_1_7_2","doi-asserted-by":"publisher","DOI":"10.1007\/BFb0086114"},{"key":"e_1_2_1_8_2","doi-asserted-by":"publisher","DOI":"10.2307\/2274578"},{"key":"e_1_2_1_9_2","doi-asserted-by":"publisher","DOI":"10.1002\/malq.19690152004"},{"key":"e_1_2_1_10_2","first-page":"85","volume-title":"Complexity of Computer Computations","author":"Karp R. M.","year":"1973"},{"key":"e_1_2_1_11_2","doi-asserted-by":"publisher","DOI":"10.2307\/1969708"},{"key":"e_1_2_1_12_2","doi-asserted-by":"publisher","DOI":"10.1145\/321864.321877"},{"key":"e_1_2_1_13_2","doi-asserted-by":"crossref","unstructured":"Ladner R. N.Lynch andA. L.Selman Comparison of polynomial time reducibilities. Proceedings Sixth Annual ACM Symposium on Theory of Computing1974 110\u2013121.","DOI":"10.1145\/800119.803891"},{"key":"e_1_2_1_14_2","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(75)90016-X"},{"key":"e_1_2_1_15_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-21755-9"},{"key":"e_1_2_1_16_2","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(82)90085-8"},{"key":"e_1_2_1_17_2","unstructured":"McEvoy K. On the structure of the enumeration degrees. Doctoral Dissertation University of Leeds 1984."},{"key":"e_1_2_1_18_2","doi-asserted-by":"publisher","DOI":"10.2307\/2273985"},{"key":"e_1_2_1_19_2","doi-asserted-by":"crossref","first-page":"519","DOI":"10.1090\/S0002-9939-1961-0125794-X","article-title":"Notes on degrees of partial functions","volume":"12","author":"Myhill J.","year":"1961","journal-title":"Proc. Amer. Math. Soc."},{"key":"e_1_2_1_20_2","volume-title":"Theory of Recursive Functions and Effective Computability","author":"Rogers H.","year":"1967"},{"key":"e_1_2_1_21_2","unstructured":"Sasso L. P. Degrees of unsolvability of partial functions. Doctoral Dissertation University of California Berkeley1971."},{"key":"e_1_2_1_22_2","doi-asserted-by":"publisher","DOI":"10.1137\/0205037"},{"key":"e_1_2_1_23_2","doi-asserted-by":"publisher","DOI":"10.1002\/malq.19710170139"},{"key":"e_1_2_1_24_2","doi-asserted-by":"publisher","DOI":"10.1137\/0207035"},{"key":"e_1_2_1_25_2","unstructured":"Shinoda J. andT. A.Slaman On the theory of the PTIME degrees of the recursive sets. To appear."},{"key":"e_1_2_1_26_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-02460-7"},{"key":"e_1_2_1_27_2","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(76)90061-X"}],"container-title":["Mathematical Logic Quarterly"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/api.wiley.com\/onlinelibrary\/tdm\/v1\/articles\/10.1002%2Fmalq.19970430302","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/onlinelibrary.wiley.com\/doi\/pdf\/10.1002\/malq.19970430302","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,10,10]],"date-time":"2023-10-10T05:38:01Z","timestamp":1696916281000},"score":1,"resource":{"primary":{"URL":"https:\/\/onlinelibrary.wiley.com\/doi\/10.1002\/malq.19970430302"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1997,1]]},"references-count":26,"journal-issue":{"issue":"3","published-print":{"date-parts":[[1997,1]]}},"alternative-id":["10.1002\/malq.19970430302"],"URL":"https:\/\/doi.org\/10.1002\/malq.19970430302","archive":["Portico"],"relation":{},"ISSN":["0942-5616","1521-3870"],"issn-type":[{"value":"0942-5616","type":"print"},{"value":"1521-3870","type":"electronic"}],"subject":[],"published":{"date-parts":[[1997,1]]}}}