On P-immunity of exponential time complete sets

DOI10.1006/jcss.1997.1488zbMath0882.68063OpenAlexW2023067253MaRDI QIDQ1362336

Nicholas Q. Tran

Publication date: 3 August 1997

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

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)

Cites Work

• Unnamed Item
• A Turing machine time hierarchy
• On one-way functions and polynomial-time isomorphisms
• Immunity of complete problems
• Complete Problems and Strong Polynomial Reducibilities
• Polynomial Time Productivity, Approximations, and Levelability
• Relativizations of the $\mathcal{P} = ?\mathcal{NP}$ Question
• On Isomorphisms and Density of $NP$ and Other Complete Sets
• Separating Nondeterministic Time Complexity Classes
• The isomorphism conjecture fails relative to a random oracle

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