Undecidability results for low complexity time classes

DOI10.1006/jcss.1999.1678zbMath0956.68061OpenAlexW2064943270MaRDI QIDQ1567411

André Nies, Rodney G. Downey

Publication date: 5 June 2000

Published in: Journal of Computer and System Sciences (Search for Journal in Brave)

Full work available at URL: https://semanticscholar.org/paper/13eb118f110fc536cffb204b983c658b596bd78a

zbMATH Keywords

Boolean algebrasdeterministic time hierarchy

Mathematics Subject Classification ID

Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Related Items

Undecidability of the structure of the Solovay degrees of c.e. reals, Effectively dense Boolean algebras and their applications

Cites Work

• Inhomogeneities in the polynomial-time degrees: The degrees of super sparse sets
• On the structure of sets in NP and other complexity classes
• Lattice-theoretic decision problems in universal algebra
• Relativized polynomial hierarchies extending two levels
• On the Structure of Polynomial Time Reducibility
• Relativizations of the $\mathcal{P} = ?\mathcal{NP}$ Question
• Intervals of the Lattice of Computably Enumerable Sets and Effective Boolean Algebras
• The theory of the polynomial many-one degrees of recursive sets is undecidable
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item