The 2024 Developer Survey results are live! See the results

Questions tagged [reductions]

A reduction is the transformation of one problem into another problem. A example of using a reduction would be to be to show if a problem P is undecidable. This would be achieved by transforming or performing a reduction of a decision problem $P$ into an undecidable problem. If this can be achieved then we have shown that this problem P is undecidable.

61 questions with no upvoted or accepted answers
Filter by
Sorted by
Tagged with
169 views

Is it possible to boost the error probability of a Consensus protocol over dynamic network?

Consider the binary consensus problem in a synchronous setting over dynamic network (thus, there are $n$ nodes, and some of them are connected by edges that may change round to round). Given a ...
• 211
474 views

• 2,281
97 views

Reducing counting minimal vertex covers to counting minimum cardinality vertex covers

Consider two problems. Problem 1: Given a graph $G = (V, E)$, find the number of minimum cardinality vertex covers of $G$. Problem 2: Given a graph $G = (V, E)$, find the number of minimal vertex ...
• 173
182 views

The graph of problem reductions

A classical approach to study the complexity of a problem $P$ is to efficiently reduce a well known problem $P'$ to $P$, thus showing that $P$ is at least as difficult as $P'$. The TCS literature ...
177 views

LogSpace reductions vs. PTime reductons for defining PSpace-completeness

Continuing https://cs.stackexchange.com/questions/90527/is-every-pspace-complete-problem-complete-with-respect-to-logspace-reductions : earlier, PSPACE-completeness was defined via logspace reductions ...
• 91
150 views

Reduce $m$-clause 3SAT to PLANAR-3SAT in $O(m^{2-\varepsilon})$

The classic reduction from 3SAT to PLANAR-3SAT requires a removal of $O(m^2)$ crossings from a rectilinear representation of 3SAT with $m$ clauses. However, the crossing number inequality suggests ...
• 828
155 views

Graph Isomorphism Algorithm of Vertex Transistive Graphs and other

What are the best known Graph-Isomorphism algorithms for below graph classes- 1.vertex-transitive, 2. edge-transitive, 3.arc-transitive (or symmetric) 4.distance-transitive. Are they GI Complete? ...
• 553
192 views

Can coNLogTime verification be used instead of PTime verification when characterising NP?

I recently read a paper that presented a proof calculus where the verification of whether a given proof is valid was NL-complete. The authors apparently decided that the checking procedure was not ...
• 3,053
86 views

Is universal hashing fully black-box reducible to error correcting code?

Fully black-box reduction is defined as in Notions of reducibility between crytpographic primitives, O. Reingold et al. Error-correcting code is used in the black-box abstract way in the sense that ...
105 views

Worst to average case reductions for quantum complexity classes

I am studying worst to average case reductions for different complexity classes. Consider quantum complexity classes like QMA, QSZK, or QIP. Is it known or believed that these classes are amenable to ...
• 173
92 views

Maximum weight triangles in dense graphs

There are multiple results (Vassilevska and Williams STOC09, for instance) on computing efficiently minimal-weight triangles (or more generally patterns) in node-weighted graphs. Several of these ...
• 1,095
698 views

Is there a tight lower bound on the complexity of SSSP on a graph?

I'm an undergrad and I'm not sure if this is the right way to ask this question. I want to know the lower bound on single-source shortest path computation in a general graph. The graph is allowed to ...
195 views

Counting reduction maintaining the length of the witness for #Knapsack

I want to know if there is counting reduction (weakly or strongly parsimonious) maintaining the length of the witness between two variations of $\#Knapsack$ problem. Let me define the problems first ...
• 153
118 views

Does GHC use graph reduction?

I have read somewhere that GHC does not use graph reduction for compiling/evaluating expressions. Is this right? If yes, what does it use as an alternative?
• 131
41 views

Statements equivalent to strongly polynomial time linear programming

Say a problem is SPT iff it admits an SPT algorithm. What statements of interest are known to be equivalent to "LP is SPT"? Examples: "linear feasibility solving is SPT" (due to ...
• 672
135 views

• 478
1 vote
65 views

Is this kind of "multi-reduction" interesting?

Given a decision problem $P$, the usual way to show that it is NP-hard is to find a known NP-hard problem $Q$, and show a polynomial-time algorithm that transforms every instance $I_Q$ of $Q$ to an ...
• 2,294
1 vote
72 views

Why is the model-checking problem for MSO $\textsf{PSPACE}$-complete?

I am currently reading "Parameterized Complexity Theory" by J. Flum and M. Grohe. In Chapter 10.3 they state in the first paragraph: Let us remind the reader that the model-checking problem ...
• 181
1 vote
78 views

Say I wanted to determine that the problem of membership in some language $L \subseteq \{0, 1\}^*$ is NP-hard. Say that I have a reduction $r: \{\text{set of quantifier free formulas} \rightarrow \{0,... 1 vote 0 answers 64 views Reduction from unweighted graphs to weighted graphs? Are there any examples where you take a problem for the unweighted case and reduce it to the weighted case? (Not the other way around). My objective is to do something similar to the following: If the ... 1 vote 0 answers 145 views A reduction from the maximum$k$-closure problem to the clique problem Fix a partially ordered set$(P, \le)$with$N$elements and real weights$w(p)$for each$p \in P$. A subset$S \subset P$is called closed if for any$x, y$with$y \in S$and$x \le y$we also ... • 111 1 vote 0 answers 59 views Reduction of irregular graphs, to regular graphs, while preserving hamiltonicity I am wondering if this is a topic that has had research done... If I could reduce irregular graphs to regular graphs (including replacing redundant node clusters with dummy nodes), while ensuring ... • 111 1 vote 0 answers 83 views Prove that finding set of$k$vertices$S$, such that$G{\setminus}S$is claw-free is NP-Complete The claw in a graph$G(V,E)$consists of a vertex$v\in V$, and it's three neighbours -$\{x_1,x_2,x_3\}\in V\setminus \{v\}$, if$\{x_1,x_2,x_3\}$form an independent set in$G$. The problem asks us ... • 201 1 vote 0 answers 466 views Reduction from k-Almost Independent Set to Independent Set The problem of$k$-Almost Independent Set is to decide whether or not$(G,m)$where$G$is a graph and$m \in \mathbb{N}$has a subset of$m$vertices that induces a subgraph with at most$k$edges. I ... • 11 1 vote 0 answers 122 views L-reduction From Matrix-Tiling To Minimal Dominating Set in Unit Disk Graph Recently I read this paper which was published in FOCS2007. In section 4, just before Theorem 4.2, the author mentioned that the gadget construction of Minimum Dominating Set in UDG is similar to ... 1 vote 0 answers 1k views Is there a reduction from a 0-1 knapsack problem to the unbounded problem? As we know, an unbounded knapsack problem could be described as:$\max \sum_{i=1}^nc_1x_i$s.t.$\sum_{i=1}^na_ix_i\le bx_i\ge0,x_i\in\mathbb Z,i=1,\cdots,n$And for an 0-1 knapsack problem, we ... 1 vote 0 answers 88 views Implication of lower bounds in Boolean circuit to other models of computation Suppose that one can prove that some hard function$f$with$n$bit input does not admit any Boolean circuit of size at most$n^t$. Then, how strong can we say about how hard$f$is in other models? ... • 1,130 0 votes 0 answers 31 views Reduction from any succinct language to tiling Given a set of colors$T = \{1, \ldots, k\}$, a set of horizontal or vertical rules$H, V \subseteq T \times T$of ordered pairs, and a chosen color$b = 1$, the tiling language is defined as follows: ... • 11 0 votes 0 answers 75 views Is a problem, that is$L$-complete under non-uniform$AC^0$reductions, necessarily outside of (non-uniform or uniform)$NC^1\$?

I don't have much intuition about non-uniformity so the question may be quite naive.
• 43