Generic complexity of undecidable problems
From MaRDI portal
Recommendations
Cites work
- Average-case complexity and decision problems in group theory.
- Generic-case complexity, decision problems in group theory, and random walks.
- scientific article; zbMATH DE number 1257634 (Why is no real title available?)
- MULTIPLICATIVE MEASURES ON FREE GROUPS
- On the strongly generic undecidability of the halting problem
- Recursive unsolvability of a problem of Thue
- The halting problem is decidable on a set of asymptotic probability one
Cited in
(36)- Følner functions and the generic word problem for finitely generated amenable groups
- Generic amplification of recursively enumerable sets
- Asymptotic density and computability
- Partial word and equality problems and Banach densities
- Generic undecidability of universal theories
- An average study of hypergraphs and their minimal transversals
- Algorithmic complexity as a criterion of unsolvability
- On the generic undecidability of the halting problem for normalized Turing machines
- Generic Kleene fixed point theorem
- Universality and almost decidability
- On hypercomputation, universal and diagonalization complete problems
- Generic case complexity of the graph isomorphism problem
- Random equations in free groups.
- Asymptotic density and the theory of computability: a partial survey
- Expander graphs in pure and applied mathematics
- Asymptotic density, computable traceability, and 1-randomness
- Generic Complexity of Undecidable Problems
- Undecidability in Some Structures Related to Computation Theory
- scientific article; zbMATH DE number 512805 (Why is no real title available?)
- ON GENERIC COMPLEXITY OF THE QUADRATIC RESIDUOSITY PROBLEM
- On generic complexity of the validity problem for Boolean formulas
- On generic complexity of the discrete logarithm problem
- ON GENERIC COMPLEXITY OF THE PROBLEM OF FINDING ROOTS IN GROUPS OF RESIDUES
- On generic undecidability of Hilbert's tenth problem for polynomial trees
- ASYMPTOTIC DENSITY AND COMPUTABLY ENUMERABLE SETS
- From bi-immunity to absolute undecidability
- The generic complexity of the bounded problem of graphs clustering
- The generic complexity of the graph triangulation problem
- Generic complexity of the word problem in some semigroups
- Algorithmically finite groups.
- On mathematical contributions of Paul E. Schupp
- Exponentially generic subsets of groups
- On generic complexity of Diophantine problem in parametric form
- Generic polynomial solvability of the compatibility problem for systems of equations over groups
- Generic case completeness
- On the strongly generic undecidability of the halting problem
This page was built for publication: Generic complexity of undecidable problems
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3503760)
