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 a undecidable problem. If this can be achieved ...
7
votes
0answers
85 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 ...
-2
votes
0answers
60 views
Why NP is not closed under Turing reduction [migrated]
The notion of polynomial time Turing reductions (Cook reductions) is an abstraction of a very intuitive concept: efficiently solving a problem by using another algorithm as a subroutine.
For ...
10
votes
1answer
127 views
What is the minimum required depth of reductions for NP-hardness of SAT?
As everyone knows,
SAT is complete for $\mathsf{NP}$ w.r.t. polynomial-time many-one reductions.
It is still complete w.r.t. $\mathsf{AC^0}$ many-one reductions.
My questions is what is the minimum ...
-4
votes
0answers
41 views
Is np-complete an equivalence class? [migrated]
So, there are multiple possible definitions of "np-complete", two of which being:
A decision problem $L$ is np-complete if and only if: $L \in \text{NP}$ and $\forall L' \in \text{NP}: L' ...
-1
votes
0answers
62 views
Undecidability of whether a given TM has only mechanically detectable loops or always halts [migrated]
This might be a bit of an abstruse question, but it's something I've been trying to prove.
I'm trying to show that it is undecidable whether a given Turing Machine is a member of the set of all ...
2
votes
1answer
135 views
Complexity reductions to Hamiltonian Path?
I am looking for a NP-hardness reduction from an arbitrary problem to the Hamiltonian Path problem such that the reduced no-instances of Hamiltonian path are "far" from having a Hamiltonian path.
Do ...
12
votes
1answer
217 views
Is there a list of canonical problems in distributed systems?
Last week, I was reading again Leslie's Lamport's 1982 trasncript of a conference he gave about Solved Problems, Unsolved Problems and Non-Problems in Concurrency. The paper is easily readable, but ...
10
votes
3answers
390 views
Subset sum vs. Subset product (strong vs. weak NP hardness)
I was hoping that some one might be able to explain to me why exactly the subset product problem is strongly NP-hard while the subset sum problem is weakly NP-hard.
Subset Sum: Given $X = ...
1
vote
0answers
79 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 ...
23
votes
3answers
540 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
votes
3answers
401 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 ...
4
votes
1answer
116 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
votes
1answer
93 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 ...
21
votes
2answers
659 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. ...
3
votes
0answers
95 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 ...
0
votes
1answer
219 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 ...
-3
votes
1answer
309 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 ...
1
vote
1answer
172 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 ...
5
votes
0answers
112 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 ...
4
votes
1answer
210 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 ...
0
votes
1answer
205 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 ...
2
votes
1answer
179 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 ...
6
votes
1answer
277 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 ...
5
votes
1answer
246 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?
7
votes
2answers
531 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 ...
8
votes
3answers
299 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 ...
10
votes
1answer
847 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 ...
7
votes
1answer
124 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?
1
vote
1answer
244 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
vote
1answer
188 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 ...
20
votes
2answers
709 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 ...
7
votes
1answer
212 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 ...
12
votes
2answers
434 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 ...
6
votes
4answers
2k 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 ...
21
votes
4answers
1k 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 ...
0
votes
1answer
298 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 ...
1
vote
1answer
271 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 ...
6
votes
0answers
207 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 ...
15
votes
3answers
317 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 ...
3
votes
2answers
360 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), ...
16
votes
3answers
543 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 ...
9
votes
1answer
549 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 ...
10
votes
5answers
420 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 ...
31
votes
2answers
2k 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 ...
2
votes
1answer
566 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 ...
8
votes
1answer
360 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 ...
2
votes
0answers
325 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 ...
21
votes
2answers
614 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 ...
6
votes
2answers
262 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 ...
0
votes
1answer
258 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:
...
