A comparison of polynomial time reducibilities

Related Items (only showing first 100 items - show all)

The complexity of online bribery in sequential elections ⋮ Uniformly hard languages. ⋮ A complexity theory for feasible closure properties ⋮ Space-efficient recognition of sparse self-reducible languages ⋮ Bi-immunity separates strong NP-completeness notions ⋮ The structure of the honest polynomial m-degrees ⋮ Locating \(P\)/poly optimally in the extended low hierarchy ⋮ On the continued fraction representation of computable real numbers ⋮ A note on complete problems for complexity classes ⋮ A comparison of polynomial time completeness notions ⋮ Genericity and measure for exponential time ⋮ Geometric sets of low information content ⋮ Quasi-linear truth-table reductions to \(p\)-selective sets ⋮ Query-monotonic Turing reductions ⋮ Geometric optimization and the polynomial hierarchy ⋮ Polynomial-time reducibilities and ``almost all oracle sets ⋮ Polynomial terse sets ⋮ Bounded truth table does not reduce the one-query tautologies to a random oracle ⋮ Geometric optimization and \(D^ P\)-completeness ⋮ More complicated questions about maxima and minima, and some closures of NP ⋮ Diagonalizations over polynomial time computable sets ⋮ Decompositions of nondeterministic reductions ⋮ Promise problems complete for complexity classes ⋮ Collapsing degrees ⋮ The logarithmic alternation hierarchy collapses: \(A\Sigma _ 2^{{\mathcal L}}=A\Pi_ 2^{{\mathcal L}}\) ⋮ The complexity of computing minimal unidirectional covering sets ⋮ A new complete language for DSPACE(log n) ⋮ Positive relativizations of the \(P=?\) NP problem ⋮ Universally serializable computation ⋮ Nontriviality for exponential time w.r.t. weak reducibilities ⋮ Indexings of subrecursive classes ⋮ P-immune sets with holes lack self-reducibility properties. ⋮ Query complexity of membership comparable sets. ⋮ On gamma-reducibility versus polynomial time many-one reducibility ⋮ Optimization problems and the polynomial hierarchy ⋮ Complexity of graph embeddability problems ⋮ Discrete extremal problems ⋮ \(P^{NP[O(\log n)}\) and sparse turing-complete sets for NP] ⋮ Honest polynomial time reducibilities and the \(P=?NP\) problem ⋮ Challenges to complexity shields that are supposed to protect elections against manipulation and control: a survey ⋮ Kolmogorov complexity and degrees of tally sets ⋮ Recursion-theoretic ranking and compression ⋮ Some observations on NP real numbers and P-selective sets ⋮ A note on sparse oracles for NP ⋮ Non-uniform reductions ⋮ Reductions on NP and p-selective sets ⋮ Bi-immunity results for cheatable sets ⋮ A survey on the structure of approximation classes ⋮ On truth-table reducibility to SAT ⋮ The complexity of manipulative attacks in nearly single-peaked electorates ⋮ Cook versus Karp-Levin: Separating completeness notions if NP is not small ⋮ Reducibility classes of P-selective sets ⋮ Computing functions with parallel queries to NP ⋮ On polynomial time one-truth-table reducibility to a sparse set ⋮ Does truth-table of linear norm reduce the one-query tautologies to a random oracle? ⋮ Autoreducibility of NP-complete sets under strong hypotheses ⋮ The p-T-degrees of the recursive sets: Lattice embeddings, extensions of embeddings and the two-quantifier theory ⋮ The complexity of unions of disjoint sets ⋮ Partial bi-immunity, scaled dimension, and NP-completeness ⋮ Collapsing and separating completeness notions under average-case and worst-case hypotheses ⋮ On sparse hard sets for counting classes ⋮ On the autoreducibility of functions ⋮ On the reducibility of sets inside NP to sets with low information content ⋮ Lower bounds and the hardness of counting properties ⋮ The fault tolerance of NP-hard problems ⋮ Survey of polynomial transformations between NP-complete problems ⋮ Complexity-theoretic aspects of expanding cellular automata ⋮ Complexity-class-encoding sets ⋮ The strong exponential hierarchy collapses ⋮ Error-bounded probabilistic computations between MA and AM ⋮ Log space machines with multiple oracle tapes ⋮ On languages specified by relative acceptance ⋮ Complexity in mechanized hypothesis formation ⋮ Hard promise problems and nonuniform complexity ⋮ On 1-truth-table-hard languages ⋮ Strong nondeterministic Turing reduction - a technique for proving intractability ⋮ Non-mitotic sets ⋮ Cook reducibility is faster than Karp reducibility in NP ⋮ Complexity of the calculus of continued fraction representation of real numbers ⋮ The price of universality ⋮ Anyone but him: the complexity of precluding an alternative ⋮ Distinguishing conjunctive and disjunctive reducibilities by sparse sets ⋮ A second step towards complexity-theoretic analogs of Rice's Theorem ⋮ Sets without subsets of higher many-one degree ⋮ The computational complexity of ideal semantics ⋮ A note on a theorem by Ladner ⋮ A low and a high hierarchy within NP ⋮ On self-reducibility and weak P-selectivity ⋮ Strong nondeterministic polynomial-time reducibilities ⋮ Some consequences of non-uniform conditions on uniform classes ⋮ Reducibilities on real numbers ⋮ On the complexity of data disjunctions. ⋮ Optimal series-parallel trade-offs for reducing a function to its own graph ⋮ Degrees of Dowd-type generic oracles ⋮ Probabilistic Turing machines and recursively enumerable Dedekind cuts ⋮ The relative power of logspace and polynomial time reductions ⋮ The recursion-theoretic structure of complexity classes ⋮ On adaptive versus nonadaptive bounded query machines ⋮ Inhomogeneities in the polynomial-time degrees: The degrees of super sparse sets ⋮ The complexity of Kemeny elections

Cites Work

This page was built for publication: A comparison of polynomial time reducibilities