On self-reducibility and weak P-selectivity

DOI10.1016/0022-0000(83)90013-2zbMath0519.68062OpenAlexW2069139349MaRDI QIDQ1054475

Ker-I. Ko

Publication date: 1983

Published in: Journal of Computer and System Sciences (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0022-0000(83)90013-2

zbMATH Keywords

lownessNPself-reducibilityP-selective setsleft Dedekind cutspolynomial-time m-completenesspolynomial-time T-completeness

Mathematics Subject Classification ID

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

Related Items

A note on bi-immunity and \(p\)-closeness of \(p\)-cheatable sets in \(P\)/poly, Continuous optimization problems and a polynomial hierarchy of real functions, AND-compression of NP-complete problems: streamlined proof and minor observations, On computing the smallest four-coloring of planar graphs and non-self-reducible sets in P, On helping by robust oracle machines, Geometric sets of low information content, Quasi-linear truth-table reductions to \(p\)-selective sets, Self-reducibility, Promise problems complete for complexity classes, Is Valiant-Vazirani's isolation probability improvable?, Self-reducible sets of small density, On polynomial-time truth-table reducibility of intractable sets to P-selective sets, Time bounded frequency computations, Query complexity of membership comparable sets., Upper bounds for the complexity of sparse and tally descriptions, A result relating disjunctive self-reducibility to P-immunity, On membership comparable sets, The consequences of eliminating NP solutions, Some connections between bounded query classes and non-uniform complexity., The Boolean hierarchy of NP-partitions, In Memoriam: Ker-I Ko (1950–2018), The Power of Self-Reducibility: Selectivity, Information, and Approximation, ADVICE FOR SEMIFEASIBLE SETS AND THE COMPLEXITY-THEORETIC COST(LESSNESS) OF ALGEBRAIC PROPERTIES, Reducibility classes of P-selective sets, Some results on selectivity and self-reducibility, Optimal advice, P-selectivity: Intersections and indices, A note on P-selective sets and closeness, On sets Turing reducible to p-selective sets, New collapse consequences of NP having small circuits, On polynomial-time Turing and many-one completeness in PSPACE, Logarithmic advice classes, Sparse selfreducible sets and nonuniform lower bounds, On the reducibility of sets inside NP to sets with low information content, Competing provers yield improved Karp-Lipton collapse results, Complexity classes of equivalence problems revisited, The communication complexity of enumeration, elimination, and selection, Choosing, agreeing, and eliminating in communication complexity, Hard promise problems and nonuniform complexity, On sets bounded truth-table reducible to $P$-selective sets, Monotonous and randomized reductions to sparse sets, A hierarchy based on output multiplicity, Derandomizing Isolation in Space-Bounded Settings, On problems without polynomial kernels, Satisfiability Allows No Nontrivial Sparsification unless the Polynomial-Time Hierarchy Collapses, One query reducibilities between partial information classes, On symmetric differences of NP-hard sets with weakly P-selective sets, Nonuniform proof systems: A new framework to describe nonuniform and probabilistic complexity classes, Reducing the number of solutions of NP functions

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• The maximum value problem and NP real numbers
• Some observations on NP real numbers and P-selective sets
• Reductions on NP and p-selective sets
• A comparison of polynomial time reducibilities
• Some lowness properties and computational complexity sequences
• A Note on Sparse Complete Sets
• On Circuit-Size Complexity and the Low Hierarchy in NP
• Relative to a Random OracleA, ${\bf P}^A \ne {\bf NP}^A \ne \text{co-}{\bf NP}^A $ with Probability 1
• Completeness, Approximation and Density
• On Isomorphisms and Density of $NP$ and Other Complete Sets
• Computational complexity, speedable and levelable sets
• P-selective sets, tally languages, and the behavior of polynomial time reducibilities onNP