On the Structure of Polynomial Time Reducibility

Cited in

(only showing first 100 items - show all)

The complexity of approximating bounded-degree Boolean \(\#\)CSP
A comparison of polynomial time reducibilities
Partial Polymorphisms and Constraint Satisfaction Problems
On simple and creative sets in NP
Counting restricted homomorphisms via Möbius inversion over matroid lattices
Honest polynomial time reducibilities and the \(P=?NP\) problem
The complexity of minimal satisfiability problems
A dichotomy for real weighted Holant problems
Many Facets of Dualities
Matrix partitions of perfect graphs
Inhomogeneities in the polynomial-time degrees: The degrees of super sparse sets
\(\mathrm P \overset {?} {=} \mathrm{NP}\)
On polynomial time isomorphisms of some new complete sets
Counting induced subgraphs: a topological approach to \#W[1]-hardness
A dichotomy result for Ramsey quantifiers
A Logical Approach to Constraint Satisfaction
Nondiamond theorems for polynomial time reducibility
The complexity of surjective homomorphism problems-a survey
Physical portrayal of computational complexity
P-selective sets, tally languages, and the behavior of polynomial time reducibilities onNP
Complexity in mechanized hypothesis formation
Approximability of clausal constraints
On the expression complexity of equivalence and isomorphism of primitive positive formulas
On languages specified by relative acceptance
On \(\Pi_ 2\) theories of \(hp-T\) degrees of low sets
Generalisations of matrix partitions: complexity and obstructions
Complexity of inverse constraint problems and a dichotomy for the inverse satisfiability problem
Tractability in constraint satisfaction problems: a survey
Characterizing polynomial Ramsey quantifiers
A note on a theorem by Ladner
The hidden subgroup problem and MKTP
Primitive recursive equivalence relations and their primitive recursive complexity
Independence results about context-free languages and lower bounds
Hardness transitions and uniqueness of acyclic colouring
Minimal pairs and complete problems
Promise constraint satisfaction: algebraic structure and a symmetric Boolean dichotomy
Is polynomial time choiceless?
Tuples of disjoint \(\mathsf{NP}\)-sets
Constructing NP-intermediate problems by blowing holes with parameters of various properties
On Ladner's result for a class of real machines with restricted use of constants
Colouring, constraint satisfaction, and complexity
\(\boldsymbol{borealis}\) -- a generalized global update algorithm for Boolean optimization problems
The birth and early years of parameterized complexity
On Ladner's result for a class of real machines with restricted use of constants
On guarded extensions of MMSNP
The complexity of weighted Boolean \#CSP with mixed signs
On the Complexity of Holant Problems
On problems without polynomial kernels
Smooth approximations: an algebraic approach to CSPs over finitely bounded homogeneous structures
scientific article; zbMATH DE number 7359806 (Why is no real title available?)
Qualitative relativizations of complexity classes
The recursion-theoretic structure of complexity classes
A dichotomy theorem for the approximate counting of complex-weighted bounded-degree Boolean CSPs
Degree theoretic definitions of the low₂ recursively enumerable sets
Log space machines with multiple oracle tapes
A dichotomy in the complexity of consistent query answering for queries with two atoms
Differences between resource bounded degree structures
Resource bounded immunity and simplicity
A characterization of the leaf language classes
A uniform approach to define complexity classes
First-order query rewriting for inconsistent databases
An approximation trichotomy for Boolean \#CSP
Polynomial and abstract subrecursive classes
Time bounded frequency computations
A Complexity Trichotomy for k-Regular Asymmetric Spin Systems Using Number Theory
Quantified Constraints in Twenty Seventeen
The complexity of tropical graph homomorphisms
Classes of bounded nondeterminism
Exact Pairs for Abstract Bounded Reducibilities
Uniformly hard languages.
Optimal satisfiability for propositional calculi and constraint satisfaction problems.
On computational complexity and honest polynomial degrees
Structure identification of Boolean relations and plain bases for co-clones
Saturation and stability in the theory of computation over the reals
On the theory of the PTIME degrees of the recursive sets
A natural encoding scheme proved probabilistic polynomial complete
The complexity of Boolean Holant problems with nonnegative weights
On guarded extensions of MMSNP
Complexity classification of local Hamiltonian problems
The p-T-degrees of the recursive sets: Lattice embeddings, extensions of embeddings and the two-quantifier theory
Parameterized counting of partially injective homomorphisms
Why is it hard to obtain a dichotomy for consistent query answering?
On Nondeterminism, Enumeration Reducibility and Polynomial Bounds
Completeness in approximation classes
Hyper-polynomial hierarchies and the polynomial jump
The \(C_{k}\)-extended graft construction
The complexity of linear programming
Discrete extremal problems
The complexity of linear programming
Weak completeness notions for exponential time
On the relative complexity of hard problems for complexity classes without complete problems
On the Hardness of Approximating Some Optimization Problems That Are Supposedly Easier Than MAX CLIQUE
On sparse sets in NP-P
Indexings of subrecursive classes
Many-one reductions and the category of multivalued functions
Computational complexity of computing symmetries in finite-domain planning
Fanout limitations on constraint systems
A survey on the structure of approximation classes
The consequences of eliminating NP solutions
Complexity of clausal constraints over chains

This page was built for publication: On the Structure of Polynomial Time Reducibility

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