Undecidability results for low complexity time classes

DOI10.1006/JCSS.1999.1678zbMATH Open0956.68061OpenAlexW2064943270MaRDI QIDQ1567411FDOQ1567411

Rodney G. Downey, André Nies

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)

Cites Work

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

Cited In (4)

• Undecidability of the structure of the Solovay degrees of c.e. reals
• Effectively dense Boolean algebras and their applications
• Undecidability over Continuous Time
• Timed Sets, Functional Complexity, and Computability

This page was built for publication: Undecidability results for low complexity time classes

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1567411)