{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,9,10]],"date-time":"2025-09-10T21:34:31Z","timestamp":1757540071307},"reference-count":15,"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":13981,"URL":"https:\/\/www.cambridge.org\/core\/terms"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["J. symb. log."],"published-print":{"date-parts":[[1975,12]]},"abstract":"<jats:p>Much recent work in the theory of computational complexity ([Me], [FR]. [SI]) is concerned with establishing \u201cthe complexity\u201d of various recursive functions, as measured by the time or space requirements of Turing machines which compute them. In the above work, we also observe another phenomenon: knowing the values of certain functions makes certain other functions easier to compute than they would be without this knowledge. We could say that the auxiliary functions \u201chelp\u201d the computation of the other functions.<\/jats:p><jats:p>For example, we may conjecture that the \u201cpolynomial-complete\u201d problems of Cook [C] and Karp [K] and Stockmeyer [S2], such as satisfiability of propositional formulas or 3-colorability of planar graphs, in fact <jats:italic>require<\/jats:italic> time proportional to <jats:italic>n<jats:sup>log<\/jats:sup><jats:sub>2<\/jats:sub><jats:sup>n<\/jats:sup><\/jats:italic> to be computed on a deterministic Turing machine. Then since the time required to decide if a planar graph with <jats:italic>n<\/jats:italic> nodes is 3-colorable can be lowered to a polynomial in <jats:italic>n<\/jats:italic> if we have a precomputed table of the satisfiable formulas in the propositional calculus, it is natural to say that the satisfiability problem \u201chelps\u201d the computation of the answers to the 3-coloring problem. Similar remarks may be made for any pair of polynomial-complete problems.<\/jats:p><jats:p>As a further illustration, Meyer and Stockmeyer [MS] have shown that, for a certain alphabet \u03a3, recognition of the set of regular expressions with squaring which are equivalent to \u03a3* requires Turing machine space <jats:italic>c<jats:sup>n<\/jats:sup><\/jats:italic> for some constant <jats:italic>c<\/jats:italic>, on an infinite set of arguments. We also know that this set of regular expressions, which we call RSQ, may actually be recognized in space <jats:italic>d<jats:sup>n<\/jats:sup><\/jats:italic> for some other constant <jats:italic>d.<\/jats:italic> Theorem 6.2 in [LMF] implies that there is some problem (not necessarily an interesting one) of complexity approximately equal to that of RSQ, which does not reduce the complexity of RSQ below <jats:italic>c<jats:sup>n<\/jats:sup><\/jats:italic>. It does not \u201chelp\u201d the computation of RSQ.<\/jats:p>","DOI":"10.2307\/2271779","type":"journal-article","created":{"date-parts":[[2006,5,6]],"date-time":"2006-05-06T17:38:25Z","timestamp":1146937105000},"page":"555-566","source":"Crossref","is-referenced-by-count":9,"title":["\u201cHelping\u201d: several formalizations"],"prefix":"10.1017","volume":"40","author":[{"given":"Nancy","family":"Lynch","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"56","published-online":{"date-parts":[[2014,3,12]]},"reference":[{"key":"S002248120005204X_ref014","doi-asserted-by":"publisher","DOI":"10.1145\/1008293.1008294"},{"key":"S002248120005204X_ref012","unstructured":"Schnorr C. P. , private communication."},{"key":"S002248120005204X_ref011","volume-title":"Theory of recursive functions and effective computability","author":"Rogers","year":"1967"},{"key":"S002248120005204X_ref010","doi-asserted-by":"crossref","unstructured":"Meyer A. and Stockmeyer L. , The equivalence problem for regular expressions with squaring requires exponential space, 13th Annual Symposium on Switching and Automata Theory, IEEE, 1972.","DOI":"10.1109\/SWAT.1972.29"},{"key":"S002248120005204X_ref006","volume-title":"Purdue University Technical Report 82","author":"Machtey"},{"key":"S002248120005204X_ref002","doi-asserted-by":"publisher","DOI":"10.1145\/800157.805047"},{"key":"S002248120005204X_ref015","volume-title":"Zeitschrift f\u00fcr Logik und mathematische Grundlagenforschung","author":"Schnorr","year":"1975"},{"key":"S002248120005204X_ref013","unstructured":"Stockmeyer L. , Ph.D. Thesis, MIT, Department of Electrical Engineering, 1974."},{"key":"S002248120005204X_ref005","volume-title":"Transactions of the American Mathematical Society","author":"Lynch"},{"key":"S002248120005204X_ref003","article-title":"Super-exponential","author":"Fischer","year":"1974","journal-title":"complexity of Presburger arithmetic"},{"key":"S002248120005204X_ref009","doi-asserted-by":"crossref","unstructured":"Meyer A. and Moll R. , Honest bounds for complexity classes of recursive functions, 13th Annual Symposium on Switching and Automata Theory, IEEE, 1972.","DOI":"10.1109\/SWAT.1972.8"},{"key":"S002248120005204X_ref008","first-page":"55","volume":"37","author":"Meyer","year":"1972","journal-title":"Computational speed-up by effective operators"},{"key":"S002248120005204X_ref001","doi-asserted-by":"publisher","DOI":"10.1145\/321386.321395"},{"key":"S002248120005204X_ref004","volume-title":"Complexity of computer computations","author":"Karp","year":"1972"},{"key":"S002248120005204X_ref007","unstructured":"Meyer A. , Weak monadic second order theory of successor is not elementary-recursive, MIT manuscript, 1972."}],"container-title":["Journal of Symbolic Logic"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.cambridge.org\/core\/services\/aop-cambridge-core\/content\/view\/S002248120005204X","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,28]],"date-time":"2019-05-28T17:42:30Z","timestamp":1559065350000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.cambridge.org\/core\/product\/identifier\/S002248120005204X\/type\/journal_article"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1975,12]]},"references-count":15,"journal-issue":{"issue":"4","published-print":{"date-parts":[[1975,12]]}},"alternative-id":["S002248120005204X"],"URL":"https:\/\/doi.org\/10.2307\/2271779","relation":{},"ISSN":["0022-4812","1943-5886"],"issn-type":[{"value":"0022-4812","type":"print"},{"value":"1943-5886","type":"electronic"}],"subject":[],"published":{"date-parts":[[1975,12]]}}}