{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,16]],"date-time":"2026-05-16T03:44:18Z","timestamp":1778903058251,"version":"3.51.4"},"reference-count":21,"publisher":"Cambridge University Press (CUP)","issue":"4","license":[{"start":{"date-parts":[[2014,3,12]],"date-time":"2014-03-12T00:00:00Z","timestamp":1394582400000},"content-version":"unspecified","delay-in-days":7041,"URL":"https:\/\/www.cambridge.org\/core\/terms"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["J. symb. log."],"published-print":{"date-parts":[[1994,12]]},"abstract":"<jats:p>A reducibility \u2264<jats:sub><jats:italic>p<\/jats:italic><\/jats:sub> is a procedure whereby a set <jats:italic>A<\/jats:italic> can be computed from a set <jats:italic>B<\/jats:italic>. The most general and most extensively studied reducibility is Turing reducibility (\u2264<jats:sub><jats:italic>T<\/jats:italic><\/jats:sub>). However, when one analyzes effectiveness considerations in classical mathematics, one often discovers that the relevant reducibilities are stronger (i.e., more restrictive) than \u2264<jats:sub><jats:italic>T<\/jats:italic><\/jats:sub>. To illustrate, in combinatorial group theory we find that the word problem is many-one reducible to the conjugacy problem, and that word problems occur in each r.e. truth table (<jats:italic>tt<\/jats:italic>-) degree (see, for example, Miller [17]).<\/jats:p><jats:p>In the present paper we are concerned with another strong reducibility: weak truth table (<jats:italic>wtt<\/jats:italic>-) reducibility. Here the reader should recall that <jats:italic>A<\/jats:italic> \u2264<jats:sub><jats:italic>wtt<\/jats:italic><\/jats:sub>, <jats:italic>\u03b2<\/jats:italic> means that there is a procedure \u03a6 and a recursive function <jats:italic>\u03c6<\/jats:italic> such that \u03a6(<jats:italic>\u03b2<\/jats:italic>) = <jats:italic>A<\/jats:italic> and for all <jats:italic>x<\/jats:italic>, the <jats:italic>u<\/jats:italic>(\u03a6(<jats:italic>\u03b2; X<\/jats:italic>)) &lt; <jats:italic>\u03c6<\/jats:italic> (<jats:italic>x<\/jats:italic>). That is, the amount of information used in the computation is bounded by <jats:italic>\u03c6<\/jats:italic>. The critical difference between truth table and weak truth table reducibilities is that for <jats:italic>tt<\/jats:italic> we will at once be \u201cgiven the whole table.\u201d Thus if \u0394 is a <jats:italic>tt<\/jats:italic>-procedure and <jats:italic>\u03b4<\/jats:italic> is its use, then for all <jats:italic>x<\/jats:italic> and all strings <jats:italic>\u03c3<\/jats:italic> of length <jats:italic>\u03b4<\/jats:italic>(<jats:italic>x<\/jats:italic>) we can figure out \u0394(<jats:italic>\u03c3<\/jats:italic>; <jats:italic>x<\/jats:italic>). On the other hand if \u0394 is merely a <jats:italic>wtt<\/jats:italic>-procedure it may be that for some string <jats:italic>\u03c3<\/jats:italic>, \u0394(<jats:italic>\u03c3<\/jats:italic>; <jats:italic>x<\/jats:italic>)\u2193, whilst for another string <jats:italic>\u03bc<\/jats:italic> of the same length it may be that \u0394{<jats:italic>\u03bc<\/jats:italic>; <jats:italic>x<\/jats:italic>) \u2191. We remark that <jats:italic>wtt<\/jats:italic>-reducibility arises very naturally both in effective algebra and in the structure of the r.e. <jats:italic>T<\/jats:italic>-degrees <jats:bold>R<\/jats:bold>. The reader should see, for instance, Downey and Remmel [3], where it is shown that the complexity of r.e. bases of an r.e. vector space <jats:italic>V<\/jats:italic> is characterised precisely by the <jats:italic>wtt<\/jats:italic>-degrees below <jats:italic>V<\/jats:italic>, and also Ladner and Sasso [14] or Downey [1], where the <jats:italic>wtt<\/jats:italic>-degrees are used to investigate cupping and capping in <jats:bold>R<\/jats:bold>.<\/jats:p>","DOI":"10.2307\/2275710","type":"journal-article","created":{"date-parts":[[2006,5,6]],"date-time":"2006-05-06T22:53:29Z","timestamp":1146956009000},"page":"1360-1382","source":"Crossref","is-referenced-by-count":1,"title":["Embedding lattices into the <i>wtt<\/i>-degrees below 0\u2032"],"prefix":"10.1017","volume":"59","author":[{"given":"Rod","family":"Downey","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Christine","family":"Haught","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"56","published-online":{"date-parts":[[2014,3,12]]},"reference":[{"key":"S0022481200019320_ref019","volume-title":"Classical recursion theory","author":"Odifreddi","year":"1989"},{"key":"S0022481200019320_ref018","doi-asserted-by":"publisher","DOI":"10.1090\/S0273-0979-1981-14863-1"},{"key":"S0022481200019320_ref015","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-21755-9"},{"key":"S0022481200019320_ref013","first-page":"507","article-title":"On tt-degrees of recursively enumerable Turing degrees","volume":"106","author":"Kobzev","year":"1978","journal-title":"Matematischeski\u012d Sbornik (Novaya Seriya)"},{"key":"S0022481200019320_ref012","doi-asserted-by":"publisher","DOI":"10.1090\/S0002-9939-1985-0781069-3"},{"key":"S0022481200019320_ref010","first-page":"987","volume":"55","author":"Haught","year":"1990","journal-title":"Undecidability and initial segments of the (r.e.) tt-degrees"},{"key":"S0022481200019320_ref009","doi-asserted-by":"publisher","DOI":"10.1090\/S0002-9947-1987-0882702-4"},{"key":"S0022481200019320_ref008","unstructured":"Haught C. A. , Turing and truth table degrees of generic and recursively enumerable sets, Ph.D. Thesis, Cornell University, Ithaca, New York, 1985."},{"key":"S0022481200019320_ref006","first-page":"121","volume-title":"Recursion theory week, Proceedings Oberwolfach, 1984","volume":"1141","author":"Fejer","year":"1985"},{"key":"S0022481200019320_ref017","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4613-9730-4_1"},{"key":"S0022481200019320_ref020","doi-asserted-by":"publisher","DOI":"10.1007\/BF02482893"},{"key":"S0022481200019320_ref002","doi-asserted-by":"publisher","DOI":"10.1112\/blms\/21.1.43"},{"key":"S0022481200019320_ref011","first-page":"223","volume-title":"Recursion theory week, Proceedings Oberwolfach, 1989","volume":"1432","author":"Haught","year":"1990"},{"key":"S0022481200019320_ref003","doi-asserted-by":"publisher","DOI":"10.1016\/0168-0072(89)90051-1"},{"key":"S0022481200019320_ref007","first-page":"187","volume-title":"Recursion theory week, Proceedings Oberwolfach, 1989","volume":"1432","author":"Fejer","year":"1990"},{"key":"S0022481200019320_ref021","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-02460-7"},{"key":"S0022481200019320_ref014","doi-asserted-by":"publisher","DOI":"10.1016\/0003-4843(75)90007-8"},{"key":"S0022481200019320_ref016","doi-asserted-by":"publisher","DOI":"10.1007\/BF01669003"},{"key":"S0022481200019320_ref004","doi-asserted-by":"publisher","DOI":"10.1007\/BFb0090937"},{"key":"S0022481200019320_ref001","doi-asserted-by":"crossref","first-page":"419","DOI":"10.1215\/ijm\/1256069291","article-title":"degrees and transfer theorems","volume":"31","author":"Downey","year":"1987","journal-title":"Illinois Journal of Mathematics"},{"key":"S0022481200019320_ref005","first-page":"69","volume-title":"Proceedings of the Fourth International Congress of Logic, Methodology and Philosophy of Science","author":"Ershov","year":"1973"}],"container-title":["Journal of Symbolic Logic"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.cambridge.org\/core\/services\/aop-cambridge-core\/content\/view\/S0022481200019320","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,15]],"date-time":"2019-05-15T00:40:59Z","timestamp":1557880859000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.cambridge.org\/core\/product\/identifier\/S0022481200019320\/type\/journal_article"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1994,12]]},"references-count":21,"journal-issue":{"issue":"4","published-print":{"date-parts":[[1994,12]]}},"alternative-id":["S0022481200019320"],"URL":"https:\/\/doi.org\/10.2307\/2275710","relation":{},"ISSN":["0022-4812","1943-5886"],"issn-type":[{"value":"0022-4812","type":"print"},{"value":"1943-5886","type":"electronic"}],"subject":[],"published":{"date-parts":[[1994,12]]}}}