On the Structure of Polynomial Time Reducibility
From MaRDI portal
Publication:4085242
DOI10.1145/321864.321877zbMath0322.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
Related Items (only showing first 100 items - show all)
Reductions among polynomial isomorphism types ⋮ Some remarks on witness functions for nonpolynomial and noncomplete sets in NP ⋮ Tractability in constraint satisfaction problems: a survey ⋮ Minimal pairs and complete problems ⋮ A characterization of the leaf language classes ⋮ On problems with short certificates ⋮ The structure of the honest polynomial m-degrees ⋮ Hard constraint satisfaction problems have hard gaps at location 1 ⋮ The complexity of weighted Boolean \#CSP with mixed signs ⋮ Some complete and intermediate polynomials in algebraic complexity theory ⋮ Honest polynomial degrees and \(P=?NP\) ⋮ A note on complete problems for complexity classes ⋮ On simple and creative sets in NP ⋮ Finding a collective set of items: from proportional multirepresentation to group recommendation ⋮ Diagonalizations over polynomial time computable sets ⋮ Strong partial clones and the time complexity of SAT problems ⋮ On the relative complexity of hard problems for complexity classes without complete problems ⋮ A natural encoding scheme proved probabilistic polynomial complete ⋮ Graph isomorphism is in the low hierarchy ⋮ Canonical disjoint NP-pairs of propositional proof systems ⋮ Time bounded frequency computations ⋮ First-order query rewriting for inconsistent databases ⋮ A dichotomy in the complexity of counting database repairs ⋮ Gap-languages and log-time complexity classes ⋮ On relationships between complexity classes of Turing machines ⋮ Indexings of subrecursive classes ⋮ Physical portrayal of computational complexity ⋮ A new line of attack on the dichotomy conjecture ⋮ Membrane fission versus cell division: when membrane proliferation is not enough ⋮ On the complexity of deciding whether the distinguishing chromatic number of a graph is at most two ⋮ On Ladner's result for a class of real machines with restricted use of constants ⋮ Discrete extremal problems ⋮ Honest polynomial time reducibilities and the \(P=?NP\) problem ⋮ A note on structure and looking back applied to the relative complexity of computable functions ⋮ A dichotomy theorem for the approximate counting of complex-weighted bounded-degree Boolean CSPs ⋮ The complexity of surjective homomorphism problems-a survey ⋮ 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 ⋮ (2+\(f\)(\(n\)))-SAT and its properties. ⋮ The consequences of eliminating NP solutions ⋮ Colouring, constraint satisfaction, and complexity ⋮ A survey on the structure of approximation classes ⋮ Optimal satisfiability for propositional calculi and constraint satisfaction problems. ⋮ On sparse sets in NP-P ⋮ An appraisal of computational complexity for operations researchers ⋮ Tuples of disjoint \(\mathsf{NP}\)-sets ⋮ On the acceptance power of regular languages ⋮ Optimal advice ⋮ Strong polynomial-time reducibility ⋮ Automorphisms in the PTIME-Turing degrees of recursive sets ⋮ The complexity types of computable sets ⋮ On the theory of average case complexity ⋮ On the complexity of generalized chromatic polynomials ⋮ The p-T-degrees of the recursive sets: Lattice embeddings, extensions of embeddings and the two-quantifier theory ⋮ Structure identification of Boolean relations and plain bases for co-clones ⋮ A uniform approach to define complexity classes ⋮ If not empty, NP-P is topologically large ⋮ Diagonalization, uniformity, and fixed-point theorems ⋮ Nondiamond theorems for polynomial time reducibility ⋮ Approximate counting for complex-weighted Boolean constraint satisfaction problems ⋮ On the expression complexity of equivalence and isomorphism of primitive positive formulas ⋮ Approximability of clausal constraints ⋮ An approximation trichotomy for Boolean \#CSP ⋮ Completeness in standard and differential approximation classes: Poly-(D)APX- and (D)PTAS-completeness ⋮ Differences between resource bounded degree structures ⋮ A comparison of polynomial time reducibilities ⋮ Polynomial and abstract subrecursive classes ⋮ Minimal pairs of polynomial degrees with subexponential complexity ⋮ Research on the efficient computation mechanism -- in the case of \(N\)-vehicle exploration problem ⋮ 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 ⋮ On the theory of the PTIME degrees of the recursive sets ⋮ Partially ordered connectives and monadic monotone strict NP ⋮ A dichotomy in the complexity of consistent query answering for queries with two atoms ⋮ Undecidability results for low complexity time classes ⋮ On problems without polynomial kernels ⋮ Properties of uniformly hard languages ⋮ Subcomplete generalizations of graph isomorphism ⋮ Counting induced subgraphs: a topological approach to \#W[1-hardness] ⋮ On the structure of \(\Delta_ 2\!^ p\) ⋮ A note on a theorem by Ladner ⋮ A low and a high hierarchy within NP ⋮ Structural properties of bounded relations with an application to NP optimization problems ⋮ Strong nondeterministic polynomial-time reducibilities ⋮ Saturation and stability in the theory of computation over the reals ⋮ Polynomial time computations in models of ET ⋮ Oracle-dependent properties of the lattice of NP sets ⋮ Minimal pairs for P ⋮ Qualitative relativizations of complexity classes ⋮ The recursion-theoretic structure of complexity classes ⋮ On \(\Pi_ 2\) theories of \(hp-T\) degrees of low sets ⋮ Completeness in approximation classes ⋮ Independence results about context-free languages and lower bounds ⋮ A dichotomy for real weighted Holant problems ⋮ Inhomogeneities in the polynomial-time degrees: The degrees of super sparse sets ⋮ \(H\)-coloring dichotomy revisited
This page was built for publication: On the Structure of Polynomial Time Reducibility
