Generic amplification of recursively enumerable sets

DOI10.1007/s10469-018-9500-yzbMath1439.03078OpenAlexW2901084331WikidataQ128905847 ScholiaQ128905847MaRDI QIDQ1731522

Alexander N. Rybalov

Publication date: 13 March 2019

Published in: Algebra and Logic (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s10469-018-9500-y

zbMATH Keywords

asymptotic densityrecursively enumerable setgeneric setgeneric computabilitygeneric amplificationsimple negligible set

Mathematics Subject Classification ID

Undecidability and degrees of sets of sentences (03D35) Recursively (computably) enumerable sets and degrees (03D25)

Related Items (2)

Symmetric matrices whose entries are linear functions ⋮ Heuristic algorithms for recognition of some cubic hypersurfaces

Cites Work

• Average-case complexity and decision problems in group theory.
• Generic complexity of Presburger arithmetic
• On the strongly generic undecidability of the halting problem
• On the generic complexity of the searching graph isomorphism problem
• Generic-case complexity, decision problems in group theory, and random walks.
• The halting problem is decidable on a set of asymptotic probability one
• Generic undecidability of existential theory of integer numbers ring
• Generic complexity of the Diophantine problem
• Generic computability, Turing degrees, and asymptotic density
• Generic complexity of undecidable problems
• ON GENERIC COMPLEXITY OF THE QUADRATIC RESIDUOSITY PROBLEM
• ON GENERIC COMPLEXITY OF THE DISCRETE LOGARITHM PROBLEM

This page was built for publication: Generic amplification of recursively enumerable sets