Pages that link to "Item:Q4085242"
From MaRDI portal
The following pages link to On the Structure of Polynomial Time Reducibility (Q4085242):
Displaying 50 items.
- A dichotomy for real weighted Holant problems (Q260401) (← links)
- Tractability in constraint satisfaction problems: a survey (Q271997) (← links)
- A characterization of the leaf language classes (Q287160) (← links)
- Finding a collective set of items: from proportional multirepresentation to group recommendation (Q334810) (← links)
- Strong partial clones and the time complexity of SAT problems (Q340559) (← links)
- A dichotomy in the complexity of counting database repairs (Q389240) (← links)
- Physical portrayal of computational complexity (Q408483) (← links)
- On Ladner's result for a class of real machines with restricted use of constants (Q418114) (← links)
- A dichotomy theorem for the approximate counting of complex-weighted bounded-degree Boolean CSPs (Q443724) (← links)
- The complexity of surjective homomorphism problems-a survey (Q444433) (← links)
- The consequences of eliminating NP solutions (Q458458) (← links)
- Colouring, constraint satisfaction, and complexity (Q458466) (← links)
- A survey on the structure of approximation classes (Q458503) (← links)
- Completeness in standard and differential approximation classes: Poly-(D)APX- and (D)PTAS-completeness (Q557903) (← links)
- Differences between resource bounded degree structures (Q558725) (← links)
- A natural encoding scheme proved probabilistic polynomial complete (Q593778) (← links)
- On the complexity of deciding whether the distinguishing chromatic number of a graph is at most two (Q626859) (← links)
- On the acceptance power of regular languages (Q672323) (← links)
- Optimal advice (Q672755) (← links)
- Strong polynomial-time reducibility (Q676314) (← links)
- Automorphisms in the PTIME-Turing degrees of recursive sets (Q676317) (← links)
- On the complexity of generalized chromatic polynomials (Q679542) (← links)
- If not empty, NP-P is topologically large (Q688157) (← links)
- Approximate counting for complex-weighted Boolean constraint satisfaction problems (Q690490) (← links)
- On the expression complexity of equivalence and isomorphism of primitive positive formulas (Q692919) (← links)
- On the theory of the PTIME degrees of the recursive sets (Q751819) (← links)
- A dichotomy in the complexity of consistent query answering for queries with two atoms (Q763497) (← links)
- Counting induced subgraphs: a topological approach to \#W[1]-hardness (Q786040) (← links)
- On the structure of \(\Delta_ 2\!^ p\) (Q789386) (← links)
- Polynomial time computations in models of ET (Q795035) (← links)
- Oracle-dependent properties of the lattice of NP sets (Q795829) (← links)
- Minimal pairs for P (Q795830) (← links)
- Completeness in approximation classes (Q811119) (← links)
- \(H\)-coloring dichotomy revisited (Q817769) (← links)
- Hard constraint satisfaction problems have hard gaps at location 1 (Q837178) (← links)
- The complexity of weighted Boolean \#CSP with mixed signs (Q837186) (← links)
- Canonical disjoint NP-pairs of propositional proof systems (Q868942) (← links)
- First-order query rewriting for inconsistent databases (Q882438) (← links)
- A new line of attack on the dichotomy conjecture (Q896081) (← links)
- Membrane fission versus cell division: when membrane proliferation is not enough (Q896708) (← links)
- Honest polynomial time reducibilities and the \(P=?NP\) problem (Q909455) (← links)
- Tuples of disjoint \(\mathsf{NP}\)-sets (Q929286) (← links)
- Structure identification of Boolean relations and plain bases for co-clones (Q955340) (← links)
- Approximability of clausal constraints (Q970111) (← links)
- An approximation trichotomy for Boolean \#CSP (Q972385) (← links)
- Partially ordered connectives and monadic monotone strict NP (Q1024818) (← links)
- On problems without polynomial kernels (Q1034099) (← links)
- Properties of uniformly hard languages (Q1041777) (← links)
- A note on a theorem by Ladner (Q1051633) (← links)
- A low and a high hierarchy within NP (Q1052097) (← links)
