On simple and creative sets in NP

DOI10.1016/0304-3975(86)90144-1zbMath0638.68034OpenAlexW2005127553MaRDI QIDQ1099614

Homer, Steven

Publication date: 1986

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0304-3975(86)90144-1

zbMATH Keywords

NP-complete setsk-creative setsk-simple sets

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Complexity of computation (including implicit computational complexity) (03D15)

Related Items

Collapsing degrees, Recursion-theoretic ranking and compression, NP-Creative sets: A new class of creative sets in NP, On p-creative sets and p-completely creative sets, Resource bounded immunity and simplicity, Completeness in approximation classes

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Oracle-dependent properties of the lattice of NP sets
• Some remarks on witness functions for nonpolynomial and noncomplete sets in NP
• A note on natural complete sets and Goedel numberings
• Immunity, Relativizations, and Nondeterminism
• Bi-immune sets for complexity classes
• Completeness, Approximation and Density
• On the Structure of Polynomial Time Reducibility
• On Isomorphisms and Density of $NP$ and Other Complete Sets
• Recursively enumerable sets of positive integers and their decision problems