Dimension and the structure of complexity classes
From MaRDI portal
Publication:6109065
DOI10.1007/s00224-022-10096-7arXiv2109.05956OpenAlexW3200027702MaRDI QIDQ6109065
Elvira Mayordomo, Neil Lutz, Jack H. Lutz
Publication date: 26 July 2023
Published in: Theory of Computing Systems (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/2109.05956
Theory of computing (68Qxx) Classical measure theory (28Axx) Computability and recursion theory (03Dxx)
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Dimension spectra of random subfractals of self-similar fractals
- A divergence formula for randomness and dimension
- Inseparability and strong hypotheses for disjoint NP pairs
- Canonical disjoint NP-pairs of propositional proof systems
- Almost everywhere high nonuniform complexity
- Oracles for structural properties: The isomorphism problem and public-key cryptography
- The dimensions of individual strings and sequences
- Bounding the dimension of points on a line
- Reductions between disjoint NP-pairs
- Fractals in Probability and Analysis
- Who Asked Us? How the Theory of Computing Answers Questions about Analysis
- Category and Measure in Complexity Classes
- THE INFORMATIONAL CONTENT OF CANONICAL DISJOINT NP-PAIRS
- The complexity of promise problems with applications to public-key cryptography
- Complexity Measures for Public-Key Cryptosystems
- P-selective sets, tally languages, and the behavior of polynomial time reducibilities onNP
- Dimension in Complexity Classes
- Compressibility and resource bounded measure
- Disjoint NP-Pairs
- Algorithmic Information, Plane Kakeya Sets, and Conditional Dimension
- Algorithmic Fractal Dimensions in Geometric Measure Theory
- Fourier Analysis and Hausdorff Dimension
- On the Computational Complexity of Algorithms
- Semirecursive Sets and Positive Reducibility
- The definition of random sequences
- Fractal Intersections and Products via Algorithmic Dimension
- Theory of semi-feasible algorithms
This page was built for publication: Dimension and the structure of complexity classes
