Abstract
We examine the following question: ‘Given a problem, is it more difficult to tell how many solutions the problem has than just deciding whether it has a solution?’. We show, that in specific cases, the question can be put into a mathematically meaningful form, namely when we can translate ‘number of solutions’ as ‘number of distinct accepting computations of a nondeterministic Turing machine’ (perhaps with appropriate weights). In this context, as we show, these questions are equivalent to problems about probabilistic machines (in the sense of Gill (9)).
In the first part of the paper we examine time-bounded computations, and justify our claim that this formalization is really the ma thematical form of the question above by exhibiting a unifying model (the treshold machine) which has a special subcases the nondeterministic and the probabilistic machines. We show that natural complete problems exist and prove some elementary properties of the model.
In the second part we examine tape-bounded machines. We show that probabilistic tape-bounded machines may be simulated by deterministic Turing machines with only a polynomial increase in the amount of tape needed. This settles an open problem of Gill's (9).
This is a very powerful and perhaps unexpected result: it is the best known situation in which we are able to show that powerful ‘extras’ like nondeterminism, get us only a polynomial improvement. The result is similar in content to Savitch's celebrated simulation of non-deterministic machines (20). The proof is completely unrelated to Savitch's (his construction does not work in the probabilistic case) and is quite involved, using some powerful recent results in complexity theory (10) (18) (4).
Chapter PDF
Similar content being viewed by others
Keywords
These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.
Bibliography
Aho, A., J.E. Hopcroft and J.D. Ullman: The design and analysis of computer algorithms. Addison Wesley, Reading 1974.
Baker, T., J. Gill and R. Solovay: Relativization of the P=?NP question. SIAM. J. COMP. 4:4, 431–442
Cook, S.A.: The complexity of theorem-proving procedures. Proc. 3rd STOC (1971) 151–158
Csanky, L.: Fast parallel matrix inversion algorithms. SIAM J. COMP. 5:4, 618–623
Eilenberg, S.: Automata, languages and programming Academic Press, N. York (1974) vol. A.
Gabow, H. N., S. N. Maheshwari and L. Osterweil: On two problems in the generation of program test paths. IEEE Trans. Software Eng. 3: 2 (sept. 1976) 227–231.
Galil, Z.: On direct encodings of nondeterministic Turing machines operating in polynomial time into P-complete problems. SIGACT News 6:1 (1974) 19–23.
Garey, M. R., D. S. Johnson and L. Stockmeyer: Some simplified NP-complete problems. Proc. 6 th STOC (1974) 47–63.
Gill, J. III: Computational complexity of probabilistic Turing machines. Proc. 6 th STOC (1974) 91–95.
Hartmanis, J. and J. Simon: On the power of multiplication in random access machines. Proc. 15 th SWAT (1974) 13–23.
Hartmanis, J. and J. Simon: On the structure of feasible computations in M. Rubinoff and M. C. Yovits (eds): Advances in Computers v. 14 Academic Press, N. York (1976) 1–43.
Hoperoft, J. E. and J. D. Ullman: Formal languages and their relation to automata. Addison-Wesley, Reading Mass 1969.
Hunt, H. B. III: On time and tape complexity of languages. Proc. 5 th STOC (1973) 10–19.
Johnson, D.: Algorithms for shortest parths. TR 73–169 Cornell U.
Karp, R. M.: Reducibility among combinatorial problems in R. E. Miller and J. W. Thatcher (eds): Complexity of computer computations. Plenum Press NY (1972) 85–104s.
Kirchoff, G.: Über die Auflösung der Gleichungen, auf welche man bei der Untersuchung der linearen Verteilung galvanischer Störme gefuhrt wird. Ann. Phys. Chem. 72 (1847) 497–508.
Meyer, A. R. and L. J. Stockmeyer: The equivalence of regular expressions with squaring requires exponential space. Proc. 13 th SWAT (1972) 125–129.
Pratt, V. R., L. Stockmeyer: A characterization of the power of vector machines. JCSS 12:2 (1976) 198–221.
Sahni, S. L.: Some related problems from network flows, game theory and integer programming. Proc. 13 th SWAT (1972) 130–138.
Savitch, W. L.: Relationships between nondeterministic an deter ministic tape complexities. JCSS 4:2 (1970) 177–192.
Sethi, R.: Complete register allocation problems. SIAM. J. Comp. 4:3 (1975) 226–248.
Stockmeyer, L. J.: The polynomial-time hierarchy. IBM Res. Rep. RC 5379.
Valiant, L. G.: Unpublished manuscript.
Author information
Authors and Affiliations
Editor information
Rights and permissions
Copyright information
© 1977 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Simon, J. (1977). On the difference between one and many. In: Salomaa, A., Steinby, M. (eds) Automata, Languages and Programming. ICALP 1977. Lecture Notes in Computer Science, vol 52. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-08342-1_37
Download citation
DOI: https://doi.org/10.1007/3-540-08342-1_37
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-08342-9
Online ISBN: 978-3-540-37305-6
eBook Packages: Springer Book Archive