On the Structure of Polynomial Time Reducibility
From MaRDI portal
Publication:4085242
DOI10.1145/321864.321877zbMATH Open0322.68028OpenAlexW2052936500WikidataQ29304727 ScholiaQ29304727MaRDI QIDQ4085242
Publication date: 1975
Published in: Journal of the ACM (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1145/321864.321877
Cited In (only showing first 100 items - show all)
- On simple and creative sets in NP
- Honest polynomial time reducibilities and the \(P=?NP\) problem
- Approximate counting for complex-weighted Boolean constraint satisfaction problems
- Primitive recursive equivalence relations and their primitive recursive complexity
- Approximability of clausal constraints
- On languages specified by relative acceptance
- On the expression complexity of equivalence and isomorphism of primitive positive formulas
- A note on a theorem by Ladner
- Independence results about context-free languages and lower bounds
- Minimal pairs and complete problems
- Tuples of disjoint \(\mathsf{NP}\)-sets
- Log space machines with multiple oracle tapes
- $$P\mathop{ =}\limits^{?}NP$$
- Time bounded frequency computations
- Polynomial and abstract subrecursive classes
- Optimal satisfiability for propositional calculi and constraint satisfaction problems.
- Discrete extremal problems
- Indexings of subrecursive classes
- Complexity of clausal constraints over chains
- Strong reducibilities
- (2+\(f\)(\(n\)))-SAT and its properties.
- A note on complete problems for complexity classes
- What makes propositional abduction tractable
- Partially ordered connectives and monadic monotone strict NP
- A new line of attack on the dichotomy conjecture
- Membrane fission versus cell division: when membrane proliferation is not enough
- Undecidability results for low complexity time classes
- The 2CNF Boolean formula satisfiability problem and the linear space hypothesis
- Counting Restricted Homomorphisms via Möbius Inversion over Matroid Lattices
- Reductions among polynomial isomorphism types
- Honest polynomial degrees and \(P=?NP\)
- Inclusion complete tally languages and the Hartmanis-Berman conjecture
- Properties of uniformly hard languages
- Diagonalization, uniformity, and fixed-point theorems
- Generality's price: Inescapable deficiencies in machine-learned programs
- Counting induced subgraphs: a topological approach to \#W[1]-hardness
- On the structure of \(\Delta_ 2\!^ p\)
- Polynomial time computations in models of ET
- Minimal pairs for P
- On the structure of sets in NP and other complexity classes
- A uniform approach to obtain diagonal sets in complexity classes
- The Complexity of Boolean Holant Problems with Nonnegative Weights
- A note on structure and looking back applied to the relative complexity of computable functions
- Title not available (Why is that?)
- Minimal pairs of polynomial degrees with subexponential complexity
- On splitting recursive sets
- Solving equation systems in ω-categorical algebras
- Optimal advice
- Automorphisms in the PTIME-Turing degrees of recursive sets
- Strong polynomial-time reducibility
- On the complexity of generalized chromatic polynomials
- If not empty, NP-P is topologically large
- A comparison of polynomial time reducibilities
- The complexity of minimal satisfiability problems
- Many Facets of Dualities
- Matrix partitions of perfect graphs
- A dichotomy for real weighted Holant problems
- A Logical Approach to Constraint Satisfaction
- Inhomogeneities in the polynomial-time degrees: The degrees of super sparse sets
- P-selective sets, tally languages, and the behavior of polynomial time reducibilities onNP
- Nondiamond theorems for polynomial time reducibility
- The complexity of surjective homomorphism problems-a survey
- Complexity in mechanized hypothesis formation
- Physical portrayal of computational complexity
- On \(\Pi_ 2\) theories of \(hp-T\) degrees of low sets
- Tractability in constraint satisfaction problems: a survey
- On Ladner's result for a class of real machines with restricted use of constants
- Colouring, constraint satisfaction, and complexity
- NP-completeness: A retrospective
- The complexity of weighted Boolean \#CSP with mixed signs
- On problems without polynomial kernels
- 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
- Resource bounded immunity and simplicity
- A dichotomy in the complexity of consistent query answering for queries with two atoms
- Differences between resource bounded degree structures
- A uniform approach to define complexity classes
- A characterization of the leaf language classes
- First-order query rewriting for inconsistent databases
- An approximation trichotomy for Boolean \#CSP
- Classes of bounded nondeterminism
- The complexity of tropical graph homomorphisms
- Uniformly hard languages.
- A Dichotomy Result for Ramsey Quantifiers
- 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
- Complexity classification of local Hamiltonian problems
- The p-T-degrees of the recursive sets: Lattice embeddings, extensions of embeddings and the two-quantifier theory
- The complexity of linear programming
- Completeness in approximation classes
- Weak completeness notions for exponential time
- Fanout limitations on constraint systems
- On the relative complexity of hard problems for complexity classes without complete problems
- On sparse sets in NP-P
- A survey on the structure of approximation classes
- The consequences of eliminating NP solutions
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)
