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.
54
questions with no upvoted or accepted answers
16
votes
0
answers
167
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
14
votes
0
answers
469
views
Is there a P-complete language X such that succinct-X is in P?
I came across a paper called "A Note on Succinct Representation of Graphs". It seems that in the discussion section they claim that for any problem $X$ that is $\mathrm{P}$-hard under projections, $\...
- 5,127
12
votes
0
answers
385
views
Invisible electric fence even if P = NP?
Scott Aaronson has suggested that one argument in favor of $\mathsf{P} \ne \mathsf{NP}$ is that there seems to be an invisible electric fence separating $\mathsf{NP}$-complete problems from problems ...
- 7,465
9
votes
0
answers
927
views
What are the best known reductions from SAT to CNF-SAT?
Problems
Let SAT denote the following problem:
Given a boolean formula, does there exist a satisfying assignment?
Let CNF-SAT denote the following problem:
Given a ...
- 5,127
9
votes
0
answers
261
views
A reduction between small cliques problems
I'm looking for a reduction that gets a graph $G=(V_G,E_G)$ and outputs a graph $H$ that satisfies the following requirements.
If $G$ contains a triangle, then $H$ contains a clique of size 9.
If $G$ ...
- 1,907
8
votes
0
answers
146
views
Can we define a meaningful concept of exptime reductions (as opposed to polytime reductions) for classes like NEXP or NEEXP?
Typically we are only interested in polytime reductions as we are usually interested in showing a reduction from one NP-problem to another.
However, if we consider larger complexity classes such as ...
- 383
8
votes
0
answers
785
views
A list of XP-hard problems
The class $XP$ is the class of problems parameterized by $k$ that can be solved in time $n^{f(k)}$ for some function $f$ (each $k$ may require a different algorithm).
In their book on parameterized ...
- 312
8
votes
0
answers
720
views
Efficient Reduction from Min Cut to st-Min Cut
I am aware that many known algorithms for min cut problem is not by reducing the problem to $st$-min cut.
But the question of efficient reduction from min cut to $st$-min cut is still interesting to ...
- 1,130
6
votes
0
answers
421
views
PSPACE completeness, with different kinds of reductions
PSPACE-complete$_{FP}$ problems are the PSPACE problems such that every other PSPACE problem can be transformed to it with a polynomial time reduction, i.e. the reduction is an algorithm $\in$ FP. ...
- 161
6
votes
0
answers
355
views
Oracle complexity classes and hardness under different notions of reduction
Let C be a complexity class, and let L be a language such that PC ⊆ PL. Then it’s natural (and easy to prove) that L is C-hard with respect to Cook reductions (polytime Turing reductions).
This ...
5
votes
0
answers
137
views
Variation of (derandomized) Valiant-Vazirani
I am interested in the following "improvement" of the Valiant-Vazirani reduction. As pointed out here, under the right derandomization assumptions one can obtain a deterministic polynomial-...
- 871
5
votes
0
answers
66
views
The complexity of tensor formula evaluation problem over an infinite field
In the paper The complexity of tensor calculus by C. Damm, M. Holzer and P. McKenzie (link), the authors reduced the problem of computing the permanent of 0/1-matrices to that of evaluating tensor ...
- 81
5
votes
0
answers
119
views
Reduction between functions that preserves time and space-complexity
Under which reduction(s) is the class $\mathsf{FTISP}(t(n), s(n))$ closed?
Let $\mathsf{FTISP}(t(n), s(n))$ the class of functions from $\{0,1\}^*$ to itself that are computable by a Turing machine ...
- 4,439
5
votes
0
answers
192
views
Is anything known about Sokoban with only 1 box?
This is intended to be a simpler version of my earlier question here.
In this post, 1-Sokoban-search is Sokoban with only 1 box, 1-Sokoban-decision is
the corresponding decision problem, and 1-Sokoban ...
user6973
5
votes
0
answers
147
views
What is the relationship between $\mathsf{L}$ reductions and $\mathsf{NC}$ reductions?
The $\mathsf{P}$-complete problems can be considered "inherently sequential". $\mathsf{P}$-completeness may be defined using either $\mathsf{NC}$ reductions or $\mathsf{L}$ reductions.
Since $\mathsf{...
- 2,281
4
votes
0
answers
93
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
4
votes
0
answers
171
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 ...
- 693
4
votes
0
answers
173
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
4
votes
0
answers
146
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 ...
- 778
4
votes
0
answers
154
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?
...
- 533
4
votes
0
answers
188
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,033
3
votes
0
answers
96
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
3
votes
0
answers
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,085
3
votes
0
answers
659
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 ...
- 31
3
votes
0
answers
194
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
2
votes
0
answers
77
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 ...
2
votes
0
answers
103
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
2
votes
0
answers
39
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 ...
- 652
2
votes
0
answers
122
views
Complexity of a sum with a product
Is the following problem NP-complete:
Input: A set of tuples $T = \left\{ t_i=(a_i,b_i) | 1\le i\le n \right\}$, an integer $k$ and numbers $C,D\in \mathbb Q_{\ge 0}$.
Question: Exists a subset $S\...
- 81
2
votes
0
answers
67
views
On reduction between two classes?
https://link.springer.com/article/10.1007/s00153-013-0351-x gives seven reductions $m,c,d,p,btt(1),\ell,tt$.
What does norm $1$ mean in $btt(1)$?
Is there illustrative examples that help understand ...
- 12.8k
2
votes
0
answers
152
views
Many-one reducibility equivalent for more general computational problems?
Many-one reducibility, denoted by $\leq_m$, is a binary relation between 2 decision problems which is defined as follows:
$L' \leq_m L$ iff there exists a computable function $f$ (called a reduction) ...
- 65
2
votes
0
answers
205
views
Reduction Unbounded Knapsack < k-Exact Unbounded Knapsack
I'd like to have an explicit reduction among these two problems:
(1) Unbounded Knapsack: Given a set of $n$ item types with weight $w_i$ and quality $q_i$ solve:
$$maximize \sum_{i=1}^n q_ix_i $$ ...
2
votes
0
answers
133
views
Complexity of Knapsack-type problem with applications to computational workflows
Consider the following problem:
Let there be a set A of $n$ items $A=\{z_1, ..., z_n\}$, and let $W$ be a strictly positive integer. Each item $z_i$ has a value $v_i$ and a weight $w_i$. Finding a ...
- 87
2
votes
0
answers
187
views
Introduction to Black-Box Separations in Cryptography
Are there any textbook-style material on black-box separations in cryptography? I tried to read the paper of Impagliazzo and Rudich but couldn't get much of it.
A previous StackExchange entry gives a ...
- 31
2
votes
0
answers
178
views
Graph partition with objective over intra-partition weights
I have a problem in which I need to find an optimal graph cut that maximizes an objective over weights not on the cut. I have looked at the literature but have not been able to find any similar ...
- 21
2
votes
1
answer
723
views
3SAT to 1-in-3SAT reduction with additonal constraints
The simplest Reduction for 3-SAT to 1-in-3-SAT reduction is as follows:
For each 3SAT clause: $x+y+z=1$
Introduce 4 new variables $\{a, b, c, d\}$ and replace original clause with below 3 clauses:
$R(...
- 468
1
vote
0
answers
72
views
Using a certificate in the proof of NP hardness
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,...
- 21
1
vote
0
answers
52
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
118
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
81
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
450
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 ...
- 11
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 b$
$x_i\ge0,x_i\in\mathbb Z,i=1,\cdots,n$
And for an 0-1 knapsack problem, we ...
- 11
1
vote
0
answers
87
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
26
views
Nonlinear GAP similar to Min-GAP but with minimum quantities and without capacity
I have $m$ items and $n$ bins where each item $i$ and bin $j$ has a value $v_{i,j}$. Each bin $j$ has a value $V_j$. I want to pack the items into the bins such that
(1) I minimize the ratio of the ...
- 115
0
votes
0
answers
55
views
Reduction from Traveling Salesman
Consider the decision problem:
"Given a complete weighted graph $G=(V,E)$, an integer $k\in\mathbb N$ and two nodes $s,t\in V$ decide if $G$ has a path of at least weight $k$"
I had to ...
- 11
0
votes
0
answers
73
views
On the Reductions of Functional complexity Classes
In Chapter 10 of Computational Complexity by Christos Papadimitriou, it is noted that reduction between problems of functional complexity classes are defined as follows:
Function problem A reduces to ...
- 21
0
votes
0
answers
61
views
Existence of W[1]-Hard construction from multiple hard problems
I am a research scholar working on parameterized complexity. Currently, I am exploring ways to prove the hardness of a problem by providing W[1]-Hard constructions. A problem is known to be fixed-...
0
votes
0
answers
195
views
3-partition problem without the restriction to triplets
In the standard 3-partition problem, there are $3 m$ integers, their sum is $m T$, and they have to be partitioned into $m$ subsets of sum $T$ and size $3$.
Consider the variant without the ...
- 2,078