TY - GEN
T1 - Generic complexity of undecidable problems
AU - Myasnikov, Alexei
PY - 2007
Y1 - 2007
N2 - 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).
AB - 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).
UR - http://www.scopus.com/inward/record.url?scp=37249065165&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=37249065165&partnerID=8YFLogxK
U2 - 10.1007/978-3-540-74510-5_41
DO - 10.1007/978-3-540-74510-5_41
M3 - Conference contribution
AN - SCOPUS:37249065165
SN - 9783540745099
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 407
EP - 417
BT - Computer Science - Theory and Applications - Second International Symposium on Computer Science in Russia, CSR 2007, Proceedings
T2 - 2nd International Symposium on Computer Science in Russia, CSR 2007
Y2 - 3 September 2007 through 7 September 2007
ER -