On P-immunity of exponential time complete sets

DOI10.1006/JCSS.1997.1488zbMATH Open0882.68063OpenAlexW2023067253MaRDI QIDQ1362336FDOQ1362336

Authors: 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

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

zbMATH Keywords

P-immunity

Mathematics Subject Classification ID

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

Cites Work

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

Cited In (3)

• Almost every set in exponential time is P-bi-immune
• Almost every set in exponential time is P-bi-immune
• Title not available (Why is that?)

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)