On the Structure of Polynomial Time Reducibility
From MaRDI portal
Cited in
(only showing first 100 items - show all)- Partially ordered connectives and monadic monotone strict NP
- On problems without polynomial kernels
- Properties of uniformly hard languages
- A note on a theorem by Ladner
- A low and a high hierarchy within NP
- Strong nondeterministic polynomial-time reducibilities
- Qualitative relativizations of complexity classes
- The recursion-theoretic structure of complexity classes
- Independence results about context-free languages and lower bounds
- Inhomogeneities in the polynomial-time degrees: The degrees of super sparse sets
- Reductions among polynomial isomorphism types
- Some remarks on witness functions for nonpolynomial and noncomplete sets in NP
- Honest polynomial degrees and \(P=?NP\)
- A note on complete problems for complexity classes
- On simple and creative sets in NP
- Diagonalizations over polynomial time computable sets
- On the relative complexity of hard problems for complexity classes without complete problems
- Graph isomorphism is in the low hierarchy
- Indexings of subrecursive classes
- Discrete extremal problems
- A note on structure and looking back applied to the relative complexity of computable functions
- The maximum value problem and NP real numbers
- On the structure of sets in NP and other complexity classes
- A uniform approach to obtain diagonal sets in complexity classes
- On sparse sets in NP-P
- An appraisal of computational complexity for operations researchers
- The complexity types of computable sets
- On the theory of average case complexity
- The p-T-degrees of the recursive sets: Lattice embeddings, extensions of embeddings and the two-quantifier theory
- A uniform approach to define complexity classes
- Diagonalization, uniformity, and fixed-point theorems
- Nondiamond theorems for polynomial time reducibility
- A comparison of polynomial time reducibilities
- Polynomial and abstract subrecursive classes
- Minimal pairs of polynomial degrees with subexponential complexity
- Log space machines with multiple oracle tapes
- On polynomial time isomorphisms of some new complete sets
- On languages specified by relative acceptance
- On splitting recursive sets
- Complexity in mechanized hypothesis formation
- Saturation and stability in the theory of computation over the reals
- On \(\Pi_ 2\) theories of \(hp-T\) degrees of low sets
- Minimal pairs and complete problems
- On problems with short certificates
- The structure of the honest polynomial m-degrees
- Time bounded frequency computations
- Gap-languages and log-time complexity classes
- (2+\(f\)(\(n\)))-SAT and its properties.
- Optimal satisfiability for propositional calculi and constraint satisfaction problems.
- Undecidability results for low complexity time classes
- Structural properties of bounded relations with an application to NP optimization problems
- On relationships between complexity classes of Turing machines
- Research on the efficient computation mechanism -- in the case of N-vehicle exploration problem
- Subcomplete generalizations of graph isomorphism
- Some aspects of studying an optimization or decision problem in different computational models
- Uniformly hard languages.
- The complexity of minimal satisfiability problems
- The complexity of approximating bounded-degree Boolean \(\#\)CSP
- Lewis dichotomies in many-valued logics
- A note on non-complete problems in \(NP_\mathbb{R}\)
- The complexity of tropical graph homomorphisms
- Dichotomy for Holant\(^\ast\) problems on the Boolean domain
- Parameterized counting of partially injective homomorphisms
- Galois connections for patterns: an algebra of labelled graphs
- ASNP: a tame fragment of existential second-order logic
- Complexity of correspondence \(H\)-colourings
- Complexity of inverse constraint problems and a dichotomy for the inverse satisfiability problem
- \(\boldsymbol{borealis}\) -- a generalized global update algorithm for Boolean optimization problems
- The \(C_{k}\)-extended graft construction
- On computational complexity and honest polynomial degrees
- Weak completeness notions for exponential time
- The hidden subgroup problem and MKTP
- Constructing NP-intermediate problems by blowing holes with parameters of various properties
- A complexity theory for feasible closure properties
- Generality's price: Inescapable deficiencies in machine-learned programs
- What makes propositional abduction tractable
- Correspondence homomorphisms to reflexive graphs
- Forbidden lifts (NP and CSP for combinatorialists)
- Matrix partitions of perfect graphs
- An explicit solution to Post's problem over the reals
- Complexity of clausal constraints over chains
- Resource bounded immunity and simplicity
- A dichotomy for real weighted Holant problems
- Tractability in constraint satisfaction problems: a survey
- The constraint satisfaction problem and universal algebra
- Complexity classification of local Hamiltonian problems
- A complete dichotomy rises from the capture of vanishing signatures
- Permutation Groups and the Graph Isomorphism Problem
- \(\mathrm P \overset {?} {=} \mathrm{NP}\)
- A characterization of the leaf language classes
- The birth and early years of parameterized complexity
- Why is it hard to obtain a dichotomy for consistent query answering?
- Is polynomial time choiceless?
- A dichotomy result for Ramsey quantifiers
- Complexity with Rod
- Many Facets of Dualities
- Many-one reductions and the category of multivalued functions
- On the CSP Dichotomy Conjecture
- Classes of bounded nondeterminism
- Finding a collective set of items: from proportional multirepresentation to group recommendation
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)
