Tag: reductions

Found 90 results for 'reductions'.

1) graph-theory - Computing the edge orbits of a graph (and discussing definitions)
2) cc.complexity-theory - Natural CLIQUE to k-Color reduction
3) complexity-classes - Complexity of reachability in directed rooted forests
4) graph-theory - Is graph automorphism Karp-reducible to graph isomorphism under hidden subgroup representation?
5) reductions - Existing implementation of Scott's reduction?
6) graph-theory - Is there a direct/natural reduction to count non-bipartite perfect matchings using the permanent?
7) cc.complexity-theory - Improving Cook's generic reduction for Clique to SAT?
8) cc.complexity-theory - Why is the reduction from 3-SAT to 3-dimensional Matching Parsimonious?
9) cc.complexity-theory - Super-logspace mapping reducibility
10) cc.complexity-theory - Subset sum vs. Subset product (strong vs. weak NP hardness)
11) np-hardness - A partition problem in which some numbers may be cut
12) cc.complexity-theory - Simple reduction to unbounded knapsack?
13) ds.algorithms - Sum-of-square-roots-hard problems?
14) cc.complexity-theory - Should reductions make us more or less optimistic for the tractability of a problem?
15) cc.complexity-theory - Reductions of hard problems to physical models
16) cc.complexity-theory - Why the reduction from MINIMUM SET COVER to MINIMUM DOMINATING SET means $c \log n$-inapproximability for MINIMUM DOMINATING SET
17) reductions - Proof of an Ising model representation of graph isomorphism problem
18) cc.complexity-theory - Verifying that a reduction is correct
19) cc.complexity-theory - Direct SAT to 3-SAT reduction
20) np-hardness - Validity of exponentiation in a polynomial time reduction
21) graph-theory - Are there subexponential algorithms for PLANAR SAT known?
22) cc.complexity-theory - Many-one reduction from inequality problem to equality problem
23) cc.complexity-theory - Is there any natural Karp reduction from Independent Set problem to SAT?
24) sat - Reducing 3-XOR-SAT to HORN-SAT
25) cc.complexity-theory - Complexity of Turing self-reducibility of Clique problem?
26) np-hardness - Can this NP-hardness proof for Super Mario Brothers (and other games) be simplified?
27) reference-request - Limited number of variable occurrences in 1-in-3 SAT
28) np-hardness - What Is the Complexity of This Two-to-One Matching Problem?
29) graph-theory - Minimal polynomial reduction of dominating set to max clique
30) cc.complexity-theory - Why do NP-complete problems not have similar approximation ratios?
31) cc.complexity-theory - What is the minimum required depth of reductions for NP-hardness of SAT?
32) cc.complexity-theory - On Random Self-reducible properties
33) cc.complexity-theory - The relationship between completeness and strength of reductions
34) cc.complexity-theory - On sparse complete sets and P vs L
35) np-hardness - What languages can be reduced to a NP-complete problem in polynomial time
36) cc.complexity-theory - Many-one reductions vs. Turing reductions to define NPC
37) cc.complexity-theory - Derandomizing Valiant-Vazirani?
38) cc.complexity-theory - Unique SAT vs Exactly $m$ models
39) cc.complexity-theory - Can strong NP-hardness really be shown using plain polytime reductions?
40) cc.complexity-theory - Problems that are NP-complete under randomized or P/poly reductions.
41) cc.complexity-theory - Lower and upper bounds on the diameter of 3-regular graphs obtained after reducing practical real world problem instances to #3-regular Vertex Cover
42) cc.complexity-theory - Counting reduction from #SAT to #HornSAT?
43) reductions - Analogues of the Berman Hartmanis conjecture and the Creativity Hypothesis
44) cc.complexity-theory - Reductions between languages of different densities?
45) cc.complexity-theory - Curious about computer-assisted NP-completeness proofs
46) cc.complexity-theory - Maximize the expected number of "losers" - Is it NP-hard?
47) np-hardness - Sampling a uniformly random satisfying assignment
48) ds.algorithms - Any SAT/SMT formulations of the VRP/VRPTW (TSP, Job-Shop-Scheduling)?
49) cc.complexity-theory - Does PPAD really capture the notion of finding another unbalanced vertex?
50) cc.complexity-theory - What does 'gadget' mean in NP-hard reduction?