On P-immunity of exponential time complete sets

DOI10.1006/JCSS.1997.1488MaRDI QIDQ1362336zbMATH OpenOpenAlexFDO

Authors Nicholas Q. Tran

Publication date 3 August 1997

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

Copyright license Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International

Full work available at URL https://doi.org/10.1006/jcss.1997.1488

zbMATH Keywords

P-immunity

Mathematics Subject Classification ID

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

Recommendations

• scientific article; zbMATH DE number 1962844
• Almost every set in exponential time is P-bi-immune
• Immunity of complete problems
• Almost every set in exponential time is P-bi-immune

Cites work

• A Turing machine time hierarchy
• Complete Problems and Strong Polynomial Reducibilities
• scientific article; zbMATH DE number 512801 (Why is no real title available?)
• Immunity of complete problems
• On Isomorphisms and Density of NP and Other Complete Sets
• On one-way functions and polynomial-time isomorphisms
• Polynomial Time Productivity, Approximations, and Levelability
• Relativizations of the $\mathcal{P} = ?\mathcal{NP}$ Question
• Separating Nondeterministic Time Complexity Classes
• The isomorphism conjecture fails relative to a random oracle

Cited in

(4)

• Immunity of complete problems
• Almost every set in exponential time is P-bi-immune
• scientific article; zbMATH DE number 1962844 (Why is no real title available?)
• Almost every set in exponential time is P-bi-immune

This page was built for publication: On P-immunity of exponential time complete sets

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