Asymptotic density and computability
type: Item
instance of: scholarly article
title: Asymptotic density and computability
zbMATH Open document ID: 1496.03168
DOI: 10.3103/S1066369X21100017
author: I. I. Batyrshin
published in: Russian Mathematics
publication date: 2022-01-14T00:00:00Z
Mathematics Subject Classification ID: 03D25
Mathematics Subject Classification ID: 03D30
Mathematics Subject Classification ID: 03D28
zbMATH DE Number: 7457373
zbMATH Keywords: asymptotic density
zbMATH Keywords: generic complexity
zbMATH Keywords: bi-immune set
zbMATH Keywords: Turing degrees
zbMATH Keywords: weakly 1-generic set
MaRDI profile type: Publication
cites work: The word problem
cites work: Q3267404
cites work: The complexity of theorem-proving procedures
cites work: Reducibility among Combinatorial Problems
cites work: Average Case Complete Problems
cites work: Smoothed analysis of algorithms
cites work: Q5770248
cites work: Q3772406
cites work: ALMOST EVERY GROUP IS HYPERBOLIC
cites work: A small simplification in hyperbolic groups
cites work: Generic-case complexity, decision problems in group theory, and random walks.
cites work: Generic computability, Turing degrees, and asymptotic density
cites work: ASYMPTOTIC DENSITY AND COMPUTABLY ENUMERABLE SETS
cites work: Nonexistence of minimal pairs for generic computability
cites work: From Bi-Immunity to Absolute Undecidability
cites work: The generic degrees of density-1 sets, and a characterization of the hyperarithmetic reals
cites work: Asymptotic density and the Ershov hierarchy
cites work: Asymptotic density, immunity and randomness
cites work: Asymptotic density and the coarse computability bound
cites work: Asymptotic density, computable traceability, and 1-randomness
cites work: Notions of robust information coding
cites work: COARSE REDUCIBILITY AND ALGORITHMIC RANDOMNESS
cites work: DENSITY-1-BOUNDING AND QUASIMINIMALITY IN THE GENERIC DEGREES
cites work: Dense computability, upper cones, and minimal pairs
cites work: The gamma question for many-one degrees
cites work: An answer to the Gamma question
cites work: A Unifying Approach to the Gamma Question
cites work: Asymptotic Density and the Theory of Computability: A Partial Survey
cites work: A MINIMAL PAIR IN THE GENERIC DEGREES
cites work: Q4040892
cites work: Q5619077
cites work: On a hierarchy of sets. III
cites work: Generic complexity of undecidable problems
cites work: Notions of weak genericity
full work available at URL: s1066369x21100017
OpenAlex ID: W3216082958
description: scientific article; zbMATH DE number 7457373