Completeness, Approximation and Density
From MaRDI portal
Publication:3922170
DOI10.1137/0210061zbMath0468.68051OpenAlexW2087899564MaRDI QIDQ3922170
No author found.
Publication date: 1981
Published in: SIAM Journal on Computing (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1137/0210061
Related Items
Reductions among polynomial isomorphism types, Some remarks on witness functions for nonpolynomial and noncomplete sets in NP, One-way permutations and self-witnessing languages, Nonlevelable sets and immune sets in the accepting density hierarchy inNP, Almost every set in exponential time is P-bi-immune, A comparison of polynomial time completeness notions, On simple and creative sets in NP, The structure of generalized complexity cores, A survey of one-way functions in complexity theory, E-complete sets do not have optimal polynomial time approximations, Sets computable in polynomial time on average, Polynomial-time axioms of choice and polynomial-time cardinality, P-immune sets with holes lack self-reducibility properties., Productive functions and isomorphisms, OnP-subset structures, Immunity and pseudorandomness of context-free languages, In Memoriam: Ker-I Ko (1950–2018), The Power of Self-Reducibility: Selectivity, Information, and Approximation, NP-Creative sets: A new class of creative sets in NP, On p-creative sets and p-completely creative sets, Immunity, simplicity, probabilistic complexity classes and relativizations, Cook versus Karp-Levin: Separating completeness notions if NP is not small, On optimal polynomial time approximations: P-levelability vs. δ-levelability, On polynomial-time Turing and many-one completeness in PSPACE, Partial bi-immunity, scaled dimension, and NP-completeness, On the polynomial IO-complexity, Hard Instances of Algorithms and Proof Systems, Cook reducibility is faster than Karp reducibility in NP, Almost every set in exponential time is P-bi-immune, Genericity, Randomness, and Polynomial-Time Approximations, On self-reducibility and weak P-selectivity, Resource bounded immunity and simplicity, Bi-immune sets for complexity classes
