Completeness, Approximation and Density
From MaRDI portal
Cited in
(33)- On self-reducibility and weak P-selectivity
- Reductions among polynomial isomorphism types
- Some remarks on witness functions for nonpolynomial and noncomplete sets in NP
- A comparison of polynomial time completeness notions
- On simple and creative sets in NP
- The structure of generalized complexity cores
- On p-creative sets and p-completely creative sets
- On polynomial-time Turing and many-one completeness in PSPACE
- Almost every set in exponential time is P-bi-immune
- P-immune sets with holes lack self-reducibility properties.
- One-way permutations and self-witnessing languages
- Partial bi-immunity, scaled dimension, and NP-completeness
- Resource bounded immunity and simplicity
- In Memoriam: Ker-I Ko (1950–2018)
- The Power of Self-Reducibility: Selectivity, Information, and Approximation
- Bi-immune sets for complexity classes
- Nonlevelable sets and immune sets in the accepting density hierarchy inNP
- OnP-subset structures
- Immunity, simplicity, probabilistic complexity classes and relativizations
- A survey of one-way functions in complexity theory
- Genericity, Randomness, and Polynomial-Time Approximations
- Productive functions and isomorphisms
- On optimal polynomial time approximations: p-levelability vs. -levelability
- NP-Creative sets: A new class of creative sets in NP
- Almost every set in exponential time is P-bi-immune
- E-complete sets do not have optimal polynomial time approximations
- On the polynomial IO-complexity
- Hard instances of algorithms and proof systems
- Sets computable in polynomial time on average
- Polynomial-time axioms of choice and polynomial-time cardinality
- Immunity and pseudorandomness of context-free languages
- Cook versus Karp-Levin: Separating completeness notions if NP is not small
- Cook reducibility is faster than Karp reducibility in NP
This page was built for publication: Completeness, Approximation and Density
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3922170)
