On Certain Polynomial-Time Truth-Table Reducibilities of Complete Sets to Sparse Sets
From MaRDI portal
Publication:3335768
DOI10.1137/0212027zbMath0545.03023OpenAlexW1986448430MaRDI QIDQ3335768
Publication date: 1983
Published in: SIAM Journal on Computing (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1137/0212027
many-one reducibilitytruth-table reducibilitypolynomial-time reducibilityNP-complete setssparse setcoNP-hard set
Analysis of algorithms and problem complexity (68Q25) Complexity of computation (including implicit computational complexity) (03D15) Other degrees and reducibilities in computability and recursion theory (03D30) Turing machines and related notions (03D10)
Related Items
Space-efficient recognition of sparse self-reducible languages, Polynomial terse sets, On intractability of the classUP, Separating NE from Some Nonuniform Nondeterministic Complexity Classes, Notes on polynomial levelability, On polynomial-time truth-table reducibility of intractable sets to P-selective sets, On the power of parity polynomial time, E-complete sets do not have optimal polynomial time approximations, On lower bounds of the closeness between complexity classes, Separating NE from some nonuniform nondeterministic complexity classes, Reducibility classes of P-selective sets, A note on P-selective sets and closeness, On polynomial time one-truth-table reducibility to a sparse set, On optimal polynomial time approximations: P-levelability vs. δ-levelability, On the power of parity polynomial time, On sparse hard sets for counting classes, The fault tolerance of NP-hard problems, The strong exponential hierarchy collapses, Reductions to sets of low information content, The Fault Tolerance of NP-Hard Problems, Monotonous and randomized reductions to sparse sets, Complete sets and closeness to complexity classes, Genericity, Randomness, and Polynomial-Time Approximations, Some consequences of non-uniform conditions on uniform 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
