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
38
votes
3
answers
986
views
Why does randomness have stronger effect on reductions than on algorithms?
It is conjectured that randomness does not extend the power of polynomial time algorithms, that is, ${\bf P}={\bf BPP}$ is conjectured to hold. On the other hand, randomness seems to have a quite ...
- 11.3k
11
votes
4
answers
904
views
Does NP-completeness/hardness have to be constructive?
Is there any $L\in {\bf NP}$ with the following properties:
It is known that $L\in {\bf P}$ implies ${\bf P}={\bf NP}$.
There is no (known) polynomial time Turing reduction of $SAT$ (or some other ${\...
- 11.3k
3
votes
1
answer
271
views
Cook reduction for search problems, by universal property?
A search problem is a relation $R\subseteq \Sigma^*\times\Sigma^*$. A function $f\colon \Sigma^*\to\Sigma^*$ solves $R$ if $(x,f(x))\in R$ for all $x\in\Sigma^*$. Define a search problem to be ...
- 3,546
-3
votes
1
answer
125
views
Difference between 'Reductions' in algebraic problems vs “Reductions” in Computational Intractability [closed]
When I read NP-completeness for the first time, I really wondered why is the concept of Reductions given such high emphasis, after all we have been looking at concepts such as reductions and 'special ...
- 103
26
votes
2
answers
6k
views
Natural CLIQUE to k-Color reduction
There is clearly a reduction from CLIQUE to k-Color because they're both NP-Complete. In fact, I can construct one by composing a reduction from CLIQUE to 3-SAT with a reduction from 3-SAT to k-Color. ...
- 448
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
8
votes
1
answer
922
views
Counting reduction from #SAT to #HornSAT?
Is it possible to find a counting reduction from #SAT to #HornSAT? I haven't found this question posted here, so decided to check if anyone has any answer to this. Let me explain what do I mean by ...
- 153
-2
votes
1
answer
1k
views
Are all complexity classes closed under a particular reduction? [closed]
We are given a ${\bf \it syntactic }$ complexity class ${\bf A}$ such that ${\bf P}$ $\subseteq$ ${\bf A}$ $\subseteq$ ${\bf PSPACE}$. Is it possible that ${\bf A}$ is ${\bf \it not}$ closed under any ...
- 2,579
1
vote
1
answer
235
views
Super-logspace mapping reducibility
There are two well-known mapping reducibilities: polytime and logspace. In both cases, the length of the output string can be at most polynomial in the length of a given input string. If we allow to ...
- 3,707
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
6
votes
1
answer
1k
views
Why the reduction from MINIMUM SET COVER to MINIMUM DOMINATING SET means $c \log n$-inapproximability for MINIMUM DOMINATING SET
There is a well-known reduction from MINIMUM SET COVER to MINIMUM DOMINATING SET provided at http://en.wikipedia.org/wiki/Dominating_set#L-reductions (attributed there to Kann 1992, but seen, for ...
2
votes
3
answers
811
views
what is "one-to-one reduction from a function f to another function g"
I am reading a paper called "Rational Proof". It mentioned the following one-to-one reduction. I cannot google an introduction of it.
An excerpt from the paper.
"Recall that a one-to-one reduction ...
- 1,443
2
votes
1
answer
278
views
Reduction/transformation from MinCostSat to MaxSat
I recently ran into MaxSAT competitions website and was looking into the problem formulation. I vaguely remember reading somewhere that MinCostSAT and MaxSAT are related to each other and one can be ...
- 121
7
votes
1
answer
633
views
More efficient Cook-Levin reduction
In the Arora-Barak book, in the Cook-Levin reduction, the resulting SAT formula is of size $T(n)\log(T(n))$, where $T(n)$ is the running time of the given Turing machine.
Is there a method to get a $...
- 163
6
votes
1
answer
412
views
Are there non-closed complexity classes for which there are complete problems?
Is saying that a class is non closed analogous to stating there are complete problems that have not been identified for that class under a certain type of reduction?
- 73
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 ...
11
votes
2
answers
2k
views
Worst case to average case reductions
Are there problems whose average case complexity is the same as their worst case complexity? What are the underlying properties of these problems that makes reducing the worst case to the average case ...
- 4,001
11
votes
3
answers
386
views
Reductions of hard problems to physical models
I am looking for examples of hard problems (in NP or harder) from computer science which can be reduced to models of physical processes.
For example, max-2-sat can be reduced to energy minimization ...
- 113
12
votes
1
answer
1k
views
Unique SAT vs Exactly $m$ models
Unique SAT is the well known problem : given a CNF formula $F$, is it true that $F$ has exactly one model ?
I am interested in « Exactly $m$-SAT » problem : given a CNF formula $F$ and an integer $m&...
7
votes
1
answer
150
views
FL with polynomial number of log-space "reductions" still in FL?
Suppose that $f: X \rightarrow X$ is computable in log-space. Given an input $x \in X$ where $x$ is encoded within $n$ bits, is $f^n(x)$ computable in log-space?
- 73
1
vote
1
answer
951
views
1- in -$k$ SAT to $k$-SAT reduction
The reduction from $k$-SAT to 1-in-$k$ SAT is known.
Would you help me to find a reduction from 1-in-$k$ SAT to $k$-SAT ? Thanks.
- 1,109
2
votes
1
answer
572
views
Lower and upper bounds on the diameter of 3-regular graphs obtained after reducing practical real world problem instances to #3-regular Vertex Cover
In the paper The diameter of random regular graphs, Bollobás and Fernandez De La Vega give asymptotic lower and upper bounds on the diameter $d$ of random $r$-regular graphs. Roughly, the lower bound ...
- 6,780
31
votes
2
answers
2k
views
Derandomizing Valiant-Vazirani?
The Valiant-Vazirani theorem says that if there is a polynomial time algorithm (deterministic or randomized) for distinguishing between a SAT formula that has exactly one satisfying assignment, and an ...
- 3,758
7
votes
1
answer
399
views
Separation between existence of crypto primitives
I understand how one can build a crypto primitive from another crypto primitive to some extent. The constructions I know build the later primitive using the former primitive as a black box. My ...
- 21.5k
17
votes
2
answers
3k
views
Can strong NP-hardness really be shown using plain polytime reductions?
I recently read a proof that intended to show that a problem was strongly NP-hard, simply by reducing to it (in polynomial time) from a strongly NP-hard problem. This didn’t make any sense to me. I ...
- 1,520
22
votes
5
answers
33k
views
Direct SAT to 3-SAT reduction
Here the goal is to reduce an arbitrary SAT problem to 3-SAT in polynomial time using the fewest number of clauses and variables. My question is motivated by curiosity. Less formally, I would like ...
- 581
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 ...
- 4,788
1
vote
1
answer
473
views
Complexity of Turing self-reducibility of Clique problem?
I'm interested in the complexity of self reducibility of a variant clique problem. Namely, the NP-complete problem HALF Clique: given a graph on $N$ nodes, Is there a clique of size $N/2$ in the graph?...
- 20.8k
1
vote
1
answer
521
views
Complexity class when reducing decision problem to function problem
Given a decision problem DEC which is PSPACE-Hard and a function problem FUN. If there is a polytime reduction from DEC to FUN, does this mean that FUN is FPSPACE-Hard?
In my case, the answer of the ...
user4388
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 ...
16
votes
3
answers
415
views
Any references for techniques in FPT reductions?
As everyone knows, Garey and Johnson's famous book (and many others) provides an excellent reference for reduction technique in classical setting. Are there any surveys or books on the
topic of ...
- 901
3
votes
2
answers
953
views
Exercises of polynomial and turing reductions
I'm following a graduated course in theoretical computer sicence. A good part the theory we see in this course has to do with polynomial and Turing reductions of NP problem (to prove NP-completeness), ...
- 133
20
votes
3
answers
1k
views
Problems that are NP-complete under randomized or P/poly reductions.
In this question, we appear to have identified a natural problem that is NP-complete under randomized reductions, but possibly not under deterministic reductions (although this depends on which ...
- 24.3k
11
votes
1
answer
832
views
Why do NP-complete problems not have similar approximation ratios?
Since 2 NP-complete problems are by definition reducible to each other, so a solution to one of them can be obtained by using a black-box solving the other one, why don't they have similar ...
- 573
11
votes
5
answers
895
views
Instance of FPT-reductions that is not a polynomial-time reduction
In parametrized complexity people use fixed-parameter-tractable (FPT) reduction to prove W[t]-hardness. Theoretically a FPT-reduction is not a polynomial-time reduction, since it can run exponentially ...
- 428
41
votes
2
answers
6k
views
Sum-of-square-roots-hard problems?
The sum of square roots problem asks, given two sequences $a_1, a_2, \dots, a_n$ and $b_1, b_2, \dots, b_n$ of positive integers, whether the sum $\sum_i \sqrt{a_i}$ less than, equal to, or greater ...
- 23.1k
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....
- 51
10
votes
1
answer
827
views
Any SAT/SMT formulations of the VRP/VRPTW (TSP, Job-Shop-Scheduling)?
i wonder if they are any approaches formulating a Vehicle-Routing-Problem with Time-Windows (VRPTW) (as a decision problem) as a SAT/SMT instance? (alternative: TSP)
For example:
"Is there a valid ...
- 203
5
votes
0
answers
902
views
Contained in NP and Turing-reduction from an NP-complete problem $\Rightarrow$ NP-complete under Karp reductions? [duplicate]
Possible Duplicates:
Do many-one reductions and Turing reductions define the same class NPC
Many-one reductions vs. Turing reductions to define NPC
Let $P,Q \subseteq \Sigma^*$ be languages ...
- 5,255
24
votes
2
answers
968
views
Is there a direct/natural reduction to count non-bipartite perfect matchings using the permanent?
Counting the number of perfect matchings in a bipartite graph is immediately reducible to computing the permanent. Since finding a perfect matching in a non-bipartite graph is in NP, there exists ...
- 2,044
6
votes
2
answers
438
views
PCPs with imperfect completeness
The traditional definition of PCPs have perfect completeness -- If $x\in L$, then the prover can give a proof on which the verifier (on reading constantly many bits) always accepts. Suppose we modify ...
- 2,482
0
votes
1
answer
1k
views
Question about Mapping Reductions (Clarify Example)
I cannot for the life of me wrap my head around these reductions.
Specifically, the example I'm wrestling with:
...
- 103
22
votes
1
answer
1k
views
Binary multiplication and parity convolution
This question is about the relationship between normal multiplication of binary numbers and polynomial multiplication mod 2. To make the question concrete, I would ideally like to know if there is a ...
- 3,950
1
vote
1
answer
1k
views
Removing all but a few cycles in a graph
Let problem $S$ be defined as
Given undirected graph $G$ and a set
of cycles $C_1,C_2, \ldots, C_n$ in G,
find minimum number of vertices that
need to be deleted to remove all
cycles in the ...
- 467
3
votes
2
answers
4k
views
Using decision version of TSP to solve optimization version
Given an oracle for solving the decision version of TSP, how would I use this to solve the optimization version of TSP.
This is not a homework assignment, but of general interest. I have been trying ...
- 171
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 ...
- 2,786
7
votes
1
answer
4k
views
Simple reduction to unbounded knapsack?
Does anyone know (or can anyone think of) a simple reduction from (for example) PARTITION, 0-1-KNAPSACK, BIN-PACKING or SUBSET-SUM (or even 3SAT) to the UBK problem (integral knapsack with unlimited ...
- 1,520
23
votes
9
answers
1k
views
Reductions from the book.
This is along the lines of "Algorithms from the Book". Although reductions are algorithms as well, I thought it doubtful that one would think of a reduction in response to the question about ...
11
votes
6
answers
2k
views
Do many-one reductions and Turing reductions define the same class NPC
I wonder if NPC classes defined by many-one reductions and Turing reductions are equal.
Edit:
Another question, are Turing reductions only collapsing C and co-C classes for some C or is there a class ...
- 1,743
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.
- 901