Completeness, Approximation and Density

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

zbMATH Keywords

polynomial time approximations to exponential time computable problems

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25)

Related Items (33)

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

This page was built for publication: Completeness, Approximation and Density