Generic case completeness
From MaRDI portal
Publication:736607
DOI10.1016/j.jcss.2016.05.002zbMath1349.68099arXiv1606.01172MaRDI QIDQ736607
Alexander Ushakov, Alexei G. Myasnikov
Publication date: 4 August 2016
Published in: Journal of Computer and System Sciences (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1606.01172
68Q25: Analysis of algorithms and problem complexity
68Q17: Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)
Related Items
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Average-case complexity and decision problems in group theory.
- Average case completeness
- Generic-case complexity, decision problems in group theory, and random walks.
- Random walk in random groups.
- Statistical properties of finitely presented groups
- The halting problem is decidable on a set of asymptotic probability one
- Small fast universal Turing machines
- Generic computability, Turing degrees, and asymptotic density
- Generic complexity of undecidable problems
- Average Case Complete Problems
- ALMOST EVERY GROUP IS HYPERBOLIC
- Generic properties of finitely presented groups and howson's theorem
- MULTIPLICATIVE MEASURES ON FREE GROUPS
- Asymptotic density and the Ershov hierarchy
- Nonexistence of minimal pairs for generic computability
- ASYMPTOTIC DENSITY AND COMPUTABLY ENUMERABLE SETS
- From Bi-Immunity to Absolute Undecidability