Generic complexity of undecidable problems

Research output: Chapter in Book/Report/Conference proceedingConference contributionpeer-review

Abstract

This is an extended abstract of my talk on generic complexity of undecidable problems. It turns out that some classical undecidable problems are, in fact, strongly undecidable, i.e., they are still undecidable on every strongly generic (i.e., "very very large") subset of inputs. For instance, the classical Halting Problem for Turing machines is strongly undecidable. Moreover, we prove an analog of the Rice's theorem for strongly undecidable problems, which provides plenty of examples of strongly undecidable problems. On the other hand, it has been shown recently that many of these classical undecidable problems are easily decidable on some generic (i.e., "very large") subsets of inputs. Altogether, these results lead to an interesting hierarchy of undecidable problems with respect to the size of subsets of inputs where the problems are still undecidable - a frequency analysis of hardness. We construct here some 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).

Original languageEnglish
Title of host publicationComputer Science - Theory and Applications - Second International Symposium on Computer Science in Russia, CSR 2007, Proceedings
Pages407-417
Number of pages11
DOIs
StatePublished - 2007
Event2nd International Symposium on Computer Science in Russia, CSR 2007 - Ekaterinburg, Russian Federation
Duration: 3 Sep 20077 Sep 2007

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume4649 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Conference

Conference2nd International Symposium on Computer Science in Russia, CSR 2007
Country/TerritoryRussian Federation
CityEkaterinburg
Period3/09/077/09/07

Fingerprint

Dive into the research topics of 'Generic complexity of undecidable problems'. Together they form a unique fingerprint.

Cite this