Hostname: page-component-78c5997874-g7gxr Total loading time: 0 Render date: 2024-11-04T18:51:08.299Z Has data issue: false hasContentIssue false
  • English
  • Français

“Helping”: several formalizations

Published online by Cambridge University Press:  12 March 2014

Nancy Lynch
Nancy Lynch*
Affiliation:
University of Southern California, los Angeles, California 90007
Get access Rights & Permissions [Opens in a new window]

Extract

Much recent work in the theory of computational complexity ([Me], [FR]. [SI]) is concerned with establishing “the complexity” 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 “help” the computation of the other functions.

For example, we may conjecture that the “polynomial-complete” problems of Cook [C] and Karp [K] and Stockmeyer [S2], such as satisfiability of propositional formulas or 3-colorability of planar graphs, in fact require time proportional to nlog2n to be computed on a deterministic Turing machine. Then since the time required to decide if a planar graph with n nodes is 3-colorable can be lowered to a polynomial in n if we have a precomputed table of the satisfiable formulas in the propositional calculus, it is natural to say that the satisfiability problem “helps” the computation of the answers to the 3-coloring problem. Similar remarks may be made for any pair of polynomial-complete problems.

As a further illustration, Meyer and Stockmeyer [MS] have shown that, for a certain alphabet Σ, recognition of the set of regular expressions with squaring which are equivalent to Σ* requires Turing machine space cn for some constant c, 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 dn for some other constant d. 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 cn . It does not “help” the computation of RSQ.

Type
Research Article
Information
The Journal of Symbolic Logic , Volume 40 , Issue 4 , December 1975 , pp. 555 - 566
Copyright
Copyright © Association for Symbolic Logic 1975

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

REFERENCES

[B] Blum, M., A machine-independent theory of the complexity of recursive functions, Journal of the Association for Computing Machinery, vol. 14 (1967), pp. 322–336.CrossRefGoogle Scholar
[C] Cook, S. A., The complexity of theorem-proving procedures, Conference Record of the Third Annual ACM Symposium on Theory of Computing, 1971, pp. 151–158.CrossRefGoogle Scholar
[FR] Fischer, M. and Rabin, M., Super-exponential complexity of Presburger arithmetic, Project MAC TM 43 (1974).Google Scholar
[K] Karp, R., Reducibility among combinatorial problems, Complexity of computer computations, Plenum, 1972.Google Scholar
[LMF] Lynch, N., Meyer, A. and Fischer, M., Relativization of the theory of computational complexity, Transactions of the American Mathematical Society (to appear).Google Scholar
[Ma] Machtey, M., The honest subrecursive classes are a lattice, Purdue University Technical Report 82.Google Scholar
[ME] Meyer, A., Weak monadic second order theory of successor is not elementary-recursive, MIT manuscript, 1972.Google Scholar
[MF] Meyer, A. and Fischer, P., Computational speed-up by effective operators, this Journal, vol. 37 (1972), pp. 55–68.Google Scholar
[MM] Meyer, A. and Moll, R., Honest bounds for complexity classes of recursive functions, 13th Annual Symposium on Switching and Automata Theory, IEEE, 1972.CrossRefGoogle Scholar
[MS] 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.Google Scholar
[R] Rogers, H., Theory of recursive functions and effective computability, McGraw-Hill, New York, 1967.Google Scholar
[S] Schnorr, C. P., private communication.Google Scholar
[SI] Stockmeyer, L., Ph.D. Thesis, MIT, Department of Electrical Engineering, 1974.Google Scholar
[S2] Stockmeyer, L., Planar three-colorability is polynomial-complete. SIGACT News, vol. 5 (1973), pp. 19–25.CrossRefGoogle Scholar
[SS] Schnorr, C. P. and Stumpf, G., A characterization of complexity sequences. Zeitschrift für Logik und mathematische Grundlagenforschung, Spring/1975.Google Scholar