Immunity of complete problems

DOI10.1006/INCO.1994.1026zbMATH Open0804.68050OpenAlexW1988256101MaRDI QIDQ1322467FDOQ1322467

Authors: Jie Wang, S. Homer 

Publication date: 12 January 1995

Published in: Information and Computation (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1006/inco.1994.1026

Recommendations

• On P-immunity of exponential time complete sets
• Properties of NP‐Complete Sets
• Immunity, Relativizations, and Nondeterminism
• Autoreducibility, mitoticity, and immunity
• Bi-immune sets for complexity classes

zbMATH Keywords

immunitydeterministic exponential timeE-complete sets

Mathematics Subject Classification ID

Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Complexity of computation (including implicit computational complexity) (03D15)

Cited In (4)

• On \(\Delta ^ P_ 2\)-immunity
• Immunity and non-cupping for closed sets
• Productive functions and isomorphisms
• On P-immunity of exponential time complete sets

This page was built for publication: Immunity of complete problems

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