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.
201
questions
0
votes
0
answers
3
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
5
votes
0
answers
113
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
11
votes
1
answer
209
views
$\mathsf{TC^0}$-completeness and reductions
AFAIU, we don't know any problem
which is complete for $\mathsf{TC^0}$ w.r.t.
many-one $\mathsf{AC^0}$ reductions ($\leq^\mathsf{AC^0}_m$).
On the other hand,
proving that they don't exist would ...
- 1,761
7
votes
1
answer
200
views
Is Circuit Minimization $P$-hard under logspace reductions?
By Circuit Minimization, I am referring to the following decision problem.
Circuit Minimization
Input: A bit string $x$ and a number $k$.
Question: Does there exist a Boolean Circuit $C$...
- 1,761
5
votes
1
answer
153
views
Are there complexity teaching resources that do not treat NP-hardness gadgets as Voodoo magic?
I am teaching a mini-complexity course to high achieving high-school students from my country this fall, and they have all expressed strong interest in learning more about what $P, NP$, reductions, ...
- 1,596
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 ...
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
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
4
votes
1
answer
69
views
Does there exist constant overhead reduction between common cryptographic primitives?
I have proved that there exist such reduction between error-correcting codes and exposure resilient functions, which is because that the transpose of a generator matrix for a ERC mapping $\mathbb{F}_2^...
- 720
2
votes
0
answers
102
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
4
votes
2
answers
422
views
Random self reducibility and NP
I was reading the Wikipedia page Random self-reducibility and it states:
If an NP-complete problem is non-adaptively random self-reducible the polynomial hierarchy collapses to $\Sigma_3$.
I am ...
CommunityBot
- 1
9
votes
1
answer
171
views
What is known about reduction by "$P_1$ interprets $P_2$" for generalized programming languages?
Inspired by this answer, let's say that a programming language is given by the data $L=(P,ev)$ where $P$ (the set of "valid programs") is a computable subset of $\Sigma^*$ and $ev$ (the "evaluator") ...
- 803
6
votes
1
answer
308
views
Unclear proof step in Feder and Greene's 1988 paper showing NP-Hardness of approximating k-center problem within a factor of 1.82
I was reading the paper "Optimal Algorithms for Approximate Clustering", Feder and Greene [1988] (https://dl.acm.org/doi/10.1145/62212.62255).
Specifically, I was trying to look at the $1.82$...
- 723
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
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
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 ...
15
votes
1
answer
949
views
Integer relation detection for Subset Sum or NPP?
Is there a way to encode an instance of Subset Sum or the Number Partition Problem so that a (small) solution to an integer relation yields an answer? If not definitely, then in some probabilistic ...
CommunityBot
- 1
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-...
1
vote
1
answer
65
views
What is region construction in timed automata?
I've recently started self-learning timed automata.
There's this theorem in there that a timed automaton can be converted to a DFA using a "region" construction. I've looked up references on ...
- 5,531
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\...
- 2,733
-1
votes
1
answer
108
views
Need more explaination on this 'generality'
I am trying to understand how this proof works
I don't understand, why this f' is nondecreasing? What kind of generality makes us come up with such kind of assumption?
Please, I am weak.
- 2,733
-1
votes
1
answer
134
views
Showing that a modification of an NP-Complete problem is also NP-Complete
In this question I give a modified version of the knapsack problem, which I call the "extended knapsack problem". I want to show that this "extended" problem is NP-Complete, but I ...
3
votes
1
answer
895
views
How to prove fooling set problem to be NP-hard
I read in a paper showing that it can be implemented by reducing induced matching problem on bipartite graphs to fooling set. But the proof was omitted in that paper and I cannot find answer by myself....
- 357
0
votes
1
answer
145
views
Parameterized complexity of Hitting Set with slightly bigger parameter
The Hitting Set problem, when parameterized by the size $k$ of the hitting set, is W[2]-hard. Is it also W[2]-hard when parameterized by $k$ plus the number of subsets in the instance?
I explain in a ...
- 3,256
4
votes
0
answers
91
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
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
-1
votes
1
answer
252
views
Does such a graph exist? [closed]
[EDITED FOR CLARITY]
Does there exist an edge-colored graph $G$ with the following properties?
$G$ has a vertex $r$ with exactly three, distinctly colored, incident edges: $(r, u)$, $(r, v)$, $(r, w)$...
- 9,595
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
1
vote
1
answer
239
views
Can this NP-hardness proof for Super Mario Brothers (and other games) be simplified?
In "Classic Nintendo Games are (Computationally) Hard", a generalized framework based on reducibility of 3-SAT for proving NP-hardness of classic Nintendo games is presented, and several ...
- 11
6
votes
1
answer
252
views
Complexity of reachability in directed rooted forests
I'm trying to figure out the complexity of the reachability problem having as input a directed rooted forest, i.e., given a set of directed rooted trees and two vertices $s$ and $t$, tell if $s$ and $...
- 16.9k
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
3
votes
1
answer
169
views
complexity class of a function - linear combinations and reductions (Fermionant, immanant, $GL_n$ representations)
The fermionant is a matrix function from physics, which is indexed by a positive integer $k$:
\begin{align}
\operatorname{Ferm}_k(A) = \sum_{\lambda} d_{\lambda}^{(k)} \operatorname{Imm}_{\lambda^T}(A)...
- 31
2
votes
1
answer
703
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
9
votes
1
answer
332
views
Existing implementation of Scott's reduction?
As per this paper by Grädel, Kolaitis and Moshe Vardi, they discuss computational complexity of satisfiability problem in $\mathrm{FO^2}$, In order to do this they use Scott's reduction. Which is the ...
- 1,330
20
votes
1
answer
1k
views
How to prove that USTCONN requires logarithmic space?
USTCONN is the problem that requires deciding whether there is a path from the source vertex $s$ to the target vertex $t$ in a graph $G$, where these are all given as part of the input.
Omer Reingold ...
- 12.8k
2
votes
2
answers
397
views
Proving not NP-complete by non-existence of gadget
Suppose we suspect a problem to be polynomial time solvable, but we are unable to prove this. So, we attempt to prove that the problem cannot be NP-hard. Known proofs in this direction show that if ...
- 36.9k
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
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
0
votes
2
answers
176
views
Knowing if there are two solutions to the subset sum problem
I was wondering if there are any results that say how hard it is to answer the question are there TWO subsets that sum to a fixed value? In other words, the subset sum problem but asking if there are ...
- 22.6k
7
votes
1
answer
347
views
Is solving the following system of boolean equations NP-hard?
I reduced a problem I'm currently working on to the following system of boolean equations:
$$
X_i \iff
\begin{cases}
\bigvee_{B \in A_i} \bigwedge_{k \in B} X_k \\
true \\
false
\end{cases}
$$
Where $|...
- 36.9k
1
vote
0
answers
71
views
Some examples of tools to demonstrate problem is in $NC$ [closed]
Unlike the class $P$ or $NP$ the class $NC$ does not have any complete problems. To show a problem is in $NC$ one needs to marshal efforts to directly show the problem is in $NC$ since there are no ...
- 12.8k
1
vote
1
answer
93
views
Can a NEXP machine simulate invalid queries to a promise problem oracle?
Let $A=(A_{YES},A_{NO})$ be some promise problem (such as xSAT, the Local Hamiltonian problem, etc). Suppose we want to show that a P machine with access to a the oracle A can always have its output ...
- 8,616
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
15
votes
2
answers
6k
views
What does 'gadget' mean in NP-hard reduction?
This question may not be technical. As a non-native speaker and a TA for algorithm class, I always wondered what gadget means in 'clause gadget' or 'variable gadget'. The dictionary says a gadget is a ...
- 36.9k
2
votes
1
answer
237
views
Is it possible to reduce an NP language to a NEXP language with exponentially smaller input length?
Suppose we have an NP-complete language $L_1$ and a NEXP-complete language $L_2$.
For any deterministic exptime machine $M_1$ with oracle access $M_1^{L_1}$, is it possible to find a deterministic ...
- 16.9k
5
votes
1
answer
1k
views
Is there any natural Karp reduction from Independent Set problem to SAT?
Is there a natural Karp reduction from Independent Set to SAT ? That is, a reduction that does not rely on the Turing machine (as the case in proof of Cook's theorem) but the combinatorial structure.
- 11.5k
13
votes
1
answer
761
views
Why is the reduction from 3-SAT to 3-dimensional Matching Parsimonious?
In this talk at the Simons Institute, Holger Dell notes that there is a parsimonious reduction from 3-SAT to the 3-dimensional Matching (3-DM) problem. In other words, there is a reduction between ...
- 9,595
1
vote
1
answer
447
views
Is the knapsack variant with small profit and unlimited repetition of items NP-hard?
Consider the unbounded Knapsack problem where we are given $n$ items of integral weights $w_i$, integral profits $p_i$, and a max weight $W$. The goal is to maximize the total profit $\sum_i x_ip_i$ ...
- 9,595
34
votes
5
answers
6k
views
Fast Reduction from RSA to SAT
Scott Aaronson's blog post today gave a list of interesting open problems/tasks in complexity. One in particular caught my attention:
Build a public library of 3SAT instances, with as few variables ...
- 103
-1
votes
1
answer
148
views
approximate maximum clique given vertex cover
I have a non optimal vertex cover of size k of a graph G, and I want to get a (1+epsilon)-approximation kernel of size linear in k for maximum clique of G. One thing I got is that every clique in G ...
- 26