A comparison of polynomial time reducibilities

Cites work

Computational Work and Time on Finite Machines
scientific article; zbMATH DE number 3560737 (Why is no real title available?)
scientific article; zbMATH DE number 3566230 (Why is no real title available?)
scientific article; zbMATH DE number 3571502 (Why is no real title available?)
scientific article; zbMATH DE number 3291134 (Why is no real title available?)
scientific article; zbMATH DE number 3311755 (Why is no real title available?)
On the Structure of Polynomial Time Reducibility
Recursively enumerable sets of positive integers and their decision problems
Relativization of the Theory of Computational Complexity
Relativizations of the $\mathcal{P} = ?\mathcal{NP}$ Question

Cited in

(only showing first 100 items - show all)

Non-mitotic sets
Anyone but him: the complexity of precluding an alternative
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
The recursion-theoretic structure of complexity classes
Inhomogeneities in the polynomial-time degrees: The degrees of super sparse sets
On the continued fraction representation of computable real numbers
A note on complete problems for complexity classes
A comparison of polynomial time completeness notions
Geometric optimization and the polynomial hierarchy
Polynomial terse sets
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
[[:Publication:1118407|The logarithmic alternation hierarchy collapses: $A\Sigma _ 2^Template:\mathcal L=A\Pi_ 2^Template:\mathcal L$]]
A new complete language for DSPACE(log n)
Positive relativizations of the $P=?$ NP problem
Indexings of subrecursive classes
On gamma-reducibility versus polynomial time many-one reducibility
Optimization problems and the polynomial hierarchy
Complexity of graph embeddability problems
Discrete extremal problems
Some observations on NP real numbers and P-selective sets
A note on sparse oracles for NP
Reductions on NP and p-selective sets
On truth-table reducibility to SAT
On polynomial time one-truth-table reducibility to a sparse set
The p-T-degrees of the recursive sets: Lattice embeddings, extensions of embeddings and the two-quantifier theory
On sparse hard sets for counting classes
Complexity-class-encoding sets
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
The relative power of logspace and polynomial time reductions
Space-efficient recognition of sparse self-reducible languages
The structure of the honest polynomial m-degrees
Locating P/poly optimally in the extended low hierarchy
Genericity and measure for exponential time
Geometric sets of low information content
Quasi-linear truth-table reductions to $p$-selective sets
Universally serializable computation
P-immune sets with holes lack self-reducibility properties.
Query complexity of membership comparable sets.
A second step towards complexity-theoretic analogs of Rice's Theorem
Recursion-theoretic ranking and compression
Autoreducibility of NP-complete sets under strong hypotheses
On the reducibility of sets inside NP to sets with low information content
Complexity of the calculus of continued fraction representation of real numbers
The price of universality
Distinguishing conjunctive and disjunctive reducibilities by sparse sets
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
Uniformly hard languages.
Bi-immunity separates strong NP-completeness notions
Non-uniform reductions
The complexity of online bribery in sequential elections
Complexity-theoretic aspects of expanding cellular automata
A complexity theory for feasible closure properties
Query-monotonic Turing reductions
Bounded truth table does not reduce the one-query tautologies to a random oracle
Challenges to complexity shields that are supposed to protect elections against manipulation and control: a survey
Partial bi-immunity, scaled dimension, and NP-completeness
Error-bounded probabilistic computations between MA and AM
Sets without subsets of higher many-one degree
Polynomial-time reducibilities and ``almost all oracle sets
On the structures inside truth-table degrees
On the definitions of some complexity classes of real numbers
Reducibilities on tally and sparse sets
Characterizing polynomial complexity classes by reducibilities
The Fault Tolerance of NP-Hard Problems
Bi-immune sets for complexity classes
Characterizations of reduction classes modulo oracle conditions
Classifying the computational complexity of problems
The difference and truth-table hierarchies for NP
Nontriviality for exponential time w.r.t. weak reducibilities
Completeness for nondeterministic complexity classes
Structural analysis of the complexity of inverse functions
Relativization of questions about log space computability
Inclusion complete tally languages and the Hartmanis-Berman conjecture
P-selective sets, tally languages, and the behavior of polynomial time reducibilities onNP
Immunity and Simplicity for Exact Counting and Other Counting Classes
Generalized theorems on relationships among reducibility notions to certain complexity classes
On the complexity of graph reconstruction
Adaptive logspace reducibility and parallel time
Time-Complexity of the Word Problem for Semigroups and the Higman Embedding Theorem
Relativized logspace and generalized quantifiers over finite ordered structures
Exact analysis of Dodgson elections: Lewis Carroll's 1876 voting system is complete for parallel access to NP
A survey on the structure of approximation classes
Fault-tolerance and complexity (extended abstract)
Bounded queries to arbitrary sets

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1223166)