{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2023,11,17]],"date-time":"2023-11-17T15:59:55Z","timestamp":1700236795876},"reference-count":23,"publisher":"World Scientific Pub Co Pte Lt","issue":"04","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Int. J. Found. Comput. Sci."],"published-print":{"date-parts":[[2000,12]]},"abstract":"<jats:p> We introduce a general framework for the definition of function classes. Our model, which is based on nondeterministic polynomial-time Turing transducers, allows uniform characterizations of FP, FP <jats:sup> NP <\/jats:sup>, FP <jats:sup> NP <\/jats:sup>[O ( log n)], [Formula: see text], counting classes (#\u00b7P, #\u00b7NP, #\u00b7coNP, GapP, GapP <jats:sup> NP <\/jats:sup>), optimization classes (max\u00b7P, min\u00b7P, max\u00b7NP, min\u00b7NP), promise classes (NPSV, #<jats:sub> few <\/jats:sub>\u00b7 P , c #\u00b7 P ), multivalued classes (FewFP, NPMV), and many more. Each such class is defined in our model by a scheme how to evaluate computation trees of nondeterministic machines. We study a reducibility notion between such evaluation schemes, which leads to a necessary and sufficient criterion for relativizable inclusion between function classes. As it turns out, this criterion is easily applicable and we get as a consequence, e.g., that there is an oracle A, such that min \u00b7 P <jats:sup>A<\/jats:sup>\u2288#\u00b7 NP <jats:sup>A<\/jats:sup> (note that no structural consequences are known to follow from the corresponding positive inclusion). <\/jats:p>","DOI":"10.1142\/s0129054100000326","type":"journal-article","created":{"date-parts":[[2002,7,27]],"date-time":"2002-07-27T07:04:45Z","timestamp":1027753485000},"page":"525-551","source":"Crossref","is-referenced-by-count":5,"title":["UNIFORM CHARACTERIZATIONS OF COMPLEXITY CLASSES OF FUNCTIONS"],"prefix":"10.1142","volume":"11","author":[{"given":"SVEN","family":"KOSUB","sequence":"first","affiliation":[{"name":"Theoretische Informatik, Julius-Maximilians-Universit\u00e4t W\u00fcrzburg, Am Hubland, D-97074 W\u00fcrzburg, Germany"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"HEINZ","family":"SCHMITZ","sequence":"additional","affiliation":[{"name":"Theoretische Informatik, Julius-Maximilians-Universit\u00e4t W\u00fcrzburg, Am Hubland, D-97074 W\u00fcrzburg, Germany"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"HERIBERT","family":"VOLLMER","sequence":"additional","affiliation":[{"name":"Theoretische Informatik, Julius-Maximilians-Universit\u00e4t W\u00fcrzburg, Am Hubland, D-97074 W\u00fcrzburg, Germany"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"219","published-online":{"date-parts":[[2011,11,20]]},"reference":[{"key":"p_3","doi-asserted-by":"publisher","DOI":"10.1137\/0213030"},{"key":"p_5","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(95)00032-R"},{"key":"p_6","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(96)00096-8"},{"key":"p_9","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(92)90125-Y"},{"key":"p_10","doi-asserted-by":"publisher","DOI":"10.1016\/S0022-0000(05)80024-8"},{"key":"p_11","first-page":"229","volume":"52","author":"Fortnow L.","year":"1994","journal-title":"Bulletin of the EATCS"},{"key":"p_13","doi-asserted-by":"publisher","DOI":"10.1145\/203610.203611"},{"key":"p_14","doi-asserted-by":"publisher","DOI":"10.1142\/S0129054100000181"},{"key":"p_18","doi-asserted-by":"publisher","DOI":"10.1006\/inco.1996.0071"},{"key":"p_19","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(94)00080-3"},{"key":"p_21","first-page":"363","volume":"26","author":"Kobler J.","year":"1989","journal-title":"Informatica"},{"key":"p_22","doi-asserted-by":"publisher","DOI":"10.1016\/S0020-0190(99)00142-8"},{"key":"p_24","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(88)90039-6"},{"key":"p_25","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(92)90073-O"},{"key":"p_29","doi-asserted-by":"publisher","DOI":"10.1016\/S0304-3975(96)00288-5"},{"key":"p_31","doi-asserted-by":"publisher","DOI":"10.1016\/S0022-0000(05)80009-1"},{"key":"p_33","doi-asserted-by":"publisher","DOI":"10.1137\/0220053"},{"key":"p_34","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(79)90044-6"},{"key":"p_35","doi-asserted-by":"publisher","DOI":"10.1137\/0208032"},{"key":"p_36","first-page":"51","volume":"57","author":"Vereshchagin N. K.","year":"1993","journal-title":"Izvestija Rossijskoj Akademii Nauk"},{"issue":"1","key":"p_38","first-page":"17","volume":"30","author":"VoUmer H.","year":"1999","journal-title":"ACM-SIC ACT Newsletter"},{"key":"p_39","doi-asserted-by":"publisher","DOI":"10.1142\/S0129054193000195"},{"key":"p_40","doi-asserted-by":"publisher","DOI":"10.1006\/inco.1995.1109"}],"container-title":["International Journal of Foundations of Computer Science"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.worldscientific.com\/doi\/pdf\/10.1142\/S0129054100000326","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,8,6]],"date-time":"2019-08-06T20:46:53Z","timestamp":1565124413000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.worldscientific.com\/doi\/abs\/10.1142\/S0129054100000326"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2000,12]]},"references-count":23,"journal-issue":{"issue":"04","published-online":{"date-parts":[[2011,11,20]]},"published-print":{"date-parts":[[2000,12]]}},"alternative-id":["10.1142\/S0129054100000326"],"URL":"https:\/\/doi.org\/10.1142\/s0129054100000326","relation":{},"ISSN":["0129-0541","1793-6373"],"issn-type":[{"value":"0129-0541","type":"print"},{"value":"1793-6373","type":"electronic"}],"subject":[],"published":{"date-parts":[[2000,12]]}}}