%0 Conference Paper %1 simon/icalp/1977 %A Simon, Janos %B Proc. of 4th Int. Coll. on Automata, Languages and Programming (ICALP) %C Berlin / Heidelberg %D 1977 %E Salomaa, Arto %E Steinby, Magnus %I Springer %K complexity counting %P 480-491 %R 10.1007/3-540-08342-1_37 %T On the difference between one and many (preliminary version) %U http://dx.doi.org/10.1007/3-540-08342-1_37 %V 52 %X 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)).

@inproceedings{simon/icalp/1977, 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)).}, added-at = {2010-09-08T10:25:21.000+0200}, address = {Berlin / Heidelberg}, affiliation = {Unicamp Dept. C. Computação Campinas SP Brasil Campinas SP Brasil}, author = {Simon, Janos}, biburl = {https://www.bibsonomy.org/bibtex/2ac7950e77de5f54061bf241a24d27dd4/mboley}, booktitle = {Proc. of 4th Int. Coll. on Automata, Languages and Programming (ICALP)}, description = {SpringerLink - Abstract}, doi = {10.1007/3-540-08342-1_37}, editor = {Salomaa, Arto and Steinby, Magnus}, interhash = {9d9b0f1191aa824a354f9a57de542fa3}, intrahash = {ac7950e77de5f54061bf241a24d27dd4}, keywords = {complexity counting}, pages = {480-491}, publisher = {Springer}, series = {Lecture Notes in Computer Science}, timestamp = {2010-09-08T10:25:21.000+0200}, title = {On the difference between one and many {(}preliminary version{)}}, url = {http://dx.doi.org/10.1007/3-540-08342-1_37}, volume = 52, year = 1977 }