Natural Self-Reducible Sets
From MaRDI portal
Publication:3816974
DOI10.1137/0217062zbMath0665.68030OpenAlexW2036878936MaRDI QIDQ3816974
Publication date: 1988
Published in: SIAM Journal on Computing (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1137/0217062
Related Items (17)
A taxonomy of complexity classes of functions ⋮ On computing the smallest four-coloring of planar graphs and non-self-reducible sets in P ⋮ Promise problems complete for complexity classes ⋮ A survey of one-way functions in complexity theory ⋮ Polynomial-time axioms of choice and polynomial-time cardinality ⋮ Bi-immunity results for cheatable sets ⋮ On quasilinear-time complexity theory ⋮ Oracles for structural properties: The isomorphism problem and public-key cryptography ⋮ On polynomial time one-truth-table reducibility to a sparse set ⋮ The complexity of unions of disjoint sets ⋮ Unions of Disjoint NP-Complete Sets ⋮ On some bandwidth restricted versions of the satisfiability problem of propositional CNF formulas ⋮ THE INFORMATIONAL CONTENT OF CANONICAL DISJOINT NP-PAIRS ⋮ Molecular computing, bounded nondeterminism, and efficient recursion ⋮ Constructing NP-intermediate problems by blowing holes with parameters of various properties ⋮ Planar graph coloring is not self-reducible, assuming P\(\neq NP\) ⋮ Padding, commitment and self-reducibility
This page was built for publication: Natural Self-Reducible Sets
