Hostname: page-component-745bb68f8f-hvd4g Total loading time: 0 Render date: 2025-01-08T22:00:15.099Z Has data issue: false hasContentIssue false
  • English
  • Français

Generic complexity of undecidable problems

Published online by Cambridge University Press:  12 March 2014

Alexei G. Myasnikov  and
Alexander N. Rybalov
Alexei G. Myasnikov
Affiliation:
Department of Mathematics and Statistics, Mcgill University, 805 Sherbrooke St. Montreal. QC, Canada, E-mail: amiasnikov@gmail.com
Alexander N. Rybalov
Affiliation:
Omsk Branch of the Institute, Of Mathematics of Siberian Branch of, Russian Academy of Science Omsk 644099, Pevtsova, 13, Russia, E-mail: alexander.rybalov@gmail.ru
Get access Rights & Permissions [Opens in a new window]

Abstract

In this paper we study generic complexity of undecidable problems. It turns out that some classical undecidable problems are, in fact, strongly undecidable, i.e., they are undecidable on every strongly generic subset of inputs. For instance, the classical Halting Problem is strongly undecidable. Moreover, we prove an analog of the Rice theorem for strongly undecidable problems, which provides plenty of examples of strongly undecidable problems. Then we show that there are natural super-undecidable problems, i.e., problem which are undecidable on every generic (not only strongly generic) subset of inputs. In particular, there are finitely presented semigroups with super-undecidable word problem. To construct strongly- and super-undecidable problems we introduce a method of generic amplification (an analog of the amplification in complexity theory). Finally, we construct absolutely undecidable problems, which stay undecidable on every non-negligible set of inputs. Their construction rests on generic immune sets.

Type
Research Article
Information
The Journal of Symbolic Logic , Volume 73 , Issue 2 , June 2008 , pp. 656 - 673
Copyright
Copyright © Association for Symbolic Logic 2008

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

[1]Adjan, S. I. and Durnev, V. G., Decision problems for groups and semigroups, Russian Mathematical Surveys, vol. 55 (2000), no. 2, pp. 207–296.Google Scholar
[2]Borovik, A., Myasnikov, A., and Remeslennikov, V. N., Multiplicative measures on free groups, International Journal of Algebra and Compututation, vol. 13 (2003), no. 6, pp. 705–731.CrossRefGoogle Scholar
[3]Borovik, A., Myasnikov, A., and Remeslennikov, V. N., Algorithmic stratification of the conjugacy problem in Miller's groups, International Journal of Algebra and Computation, to appear.Google Scholar
[4]Borovik, A., Myasnikov, A., and Shpilrain, V., Measuring sets in infinite groups, Computational and Statistical Group Theory, Contemporary Mathematics, vol. 298, 2002, pp. 21–42.CrossRefGoogle Scholar
[5]Cooper, S. B., Computability Ttheory, Chapman and Hall/CRC, 2003.Google Scholar
[6]Gilman, R., Miasnikov, A. D., Myasnikov, A. G., and Ushakov, A., Generic complexity, preprint.Google Scholar
[7]Hamkins, J. D. and Miasnikov, A. D., The halting problem is decidable on a set of asymptotic probability one, Notre Dame Journal of Formal Logic, vol. 47 (2006), no. 4, pp. 515–524.CrossRefGoogle Scholar
[8]Kapovich, I., Myasnikov, A., Schupp, P., and Shpilrain, V., Generic-case complexity and decision problems in group theory. Journal of Algebra, vol. 264 (2003), pp. 665–694.CrossRefGoogle Scholar
[9]Kapovich, I., Myasnikov, A., Schupp, P., and Shpilrain, V., Average-case complexity for the word and membership problems in group theory, Advances in Mathematics, vol. 190 (2005), no. 2, pp. 343–359.CrossRefGoogle Scholar
[10]Knuth, D. E., The Art of Computer Programming. Vol.3: Sorting and Searching, Addison-Wesley, 1998.Google Scholar
[11]Markov, A. A., On the impossibility of certain algorithms in the theory of associative systems, Doklady Akademii Nauk SSSR, vol. 55 (1947), pp. 587–590.Google Scholar
[12]Matiyasevich, Y. V., Simple examples of undecidable associative calculi, Doklady Akademii Nauk SSSR, vol. 173 (1967), pp. 1264–1266.Google Scholar
[13]Mendflson, E., Introduction to Mathematical Logic, Chapman and Hall/CRC, 1997.Google Scholar
[14]Miasnikov, A., Ushakov, A., and Won, D. W., Generic complexity of the word problem in finitely presented semigroups, 2006, preprint.Google Scholar
[15]Post, E. L., Recursive unsolvability of a problem of Thue, this Journal, vol. 12 (1947), no. 1, pp. 1–11.Google Scholar
[16]Rybalov, A., On the strongly generic undecidability of the halting problem, Theoretical Computer Science, vol. 377 (2007), no. 1-3, pp. 268–270.CrossRefGoogle Scholar
[17]Savage, J. E., The Complexity of Computing, John Wiley and Sons Inc., 1977.Google Scholar
[18]Tseitin, G. S., An associative system with undecidable equivalence problem, Reports of Mathematical Institute of Soviet Academy of Science, vol. 52 (1958), pp. 172–189.Google Scholar