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.
34
questions
43
votes
7
answers
7k
views
Many-one reductions vs. Turing reductions to define NPC
Why do most people prefer to use many-one reductions to define NP-completeness instead of, for instance, Turing reductions?
- 1,658
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
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
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
15
votes
3
answers
4k
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 = \{x_1,...,...
- 315
13
votes
2
answers
609
views
Does PPAD really capture the notion of finding another unbalanced vertex?
Complexity class PPAD was invented by Christos Papadimitriou in his seminal 1994 paper. The class is designed to capture the complexity of search problems where the existence of a solution is ...
- 546
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
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
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
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
29
votes
7
answers
2k
views
Nontrivial membership in NP
Is there an example of a language which is in $NP$, but where we cannot prove this fact directly by showing that there exists a polynomial witness for membership in this language?
Instead, the fact ...
- 8,598
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
26
votes
6
answers
2k
views
Advanced techniques for determining complexity lower bounds
Some of you may have been following this question, which was closed due to not being research level. So, I'm extracting the part of the question which is at a research level.
Beyond the "simpler" ...
- 2,830
13
votes
3
answers
343
views
Can limit of hard languages be easy?
Can the following all hold simultaneously?
$L_s$ is contained in $L_{s+1}$ for all positive integers $s$.
$L = \bigcup_s L_s$ is the language of all finite words over $\{0,1\}$.
There is some ...
- 18.9k
12
votes
3
answers
1k
views
Transitive feedback arc set (TFAS): NP-complete?
Some time ago, I posted a reference request for graph problems where we want to find a 2-partition of the edges where both sets fulfill a property not related to their cardinality. I was trying to ...
- 431
11
votes
2
answers
2k
views
Limited number of variable occurrences in 1-in-3 SAT
Is there a known result on complexity class of 1-in-3-SAT with restricted number of variable occurrences?
I've come up with the following parsimonious reduction with Peter Nightingale, but I want ...
- 428
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
10
votes
2
answers
3k
views
Proof for Kolmogorov complexity is uncomputable using reductions
I am looking for a proof that Kolmogorov complexity is uncomputable using a reduction from another uncomputable problem. The common proof is a formalization of Berry's paradox rather than a reduction, ...
- 115
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
2
answers
1k
views
Isn't it "trivial" to represent/reduce any classical physics problem into a Spin-Glass which is NP-Complete?
In the late 80's there were several highly cited efforts to use Spin-Glass models to formulate other computational problems such as: Protein Folding and Neural Networks.
Isn't it straight forward to ...
- 463
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
7
votes
1
answer
736
views
Minimal polynomial reduction of dominating set to max clique
Let $G$ be a simple undirected graph. Recall that $S \subseteq V(G)$ is a dominating set of $G$ if every vertex of $v \in V(G) \setminus S$ has a neighbour in $S.$
It is well known that it is NP ...
- 641
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
2
answers
439
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
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
5
votes
1
answer
349
views
Reduction SAT to a problem on a planar graph with as few vertices as possible
Let $\phi$ be CNF formula with $n$ variables and $m$ clauses.
I am looking for a reduction is $\phi$ satisfiable to a problem
on a planar graph $G$ with as few vertices as possible.
The majority of ...
- 1,955
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
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
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
2
votes
1
answer
169
views
What is conjunctive truth table reduction?
What are conjunctive/disjunctive truth table reductions and how do they compare with other reductions?
- 12.8k
2
votes
1
answer
450
views
Is there a FNP problem that's NP-hard but not FNP-hard?
For the reductions, choose a class C such that [it's clear what FC means]
and FC is not known to be able to solve the satisfaction search problem,
and assume that FC indeed can't solve that search ...
user6973
2
votes
1
answer
2k
views
Is there simple reduction Dominating Set to Vertex Cover?
Is there simple reduction Dominating Set to Vertex Cover?
In the other direction the reduction is simple.
Searching the web returned blog.
It warns This is not finished yet and experiments suggest
...
- 1,955
1
vote
1
answer
276
views
Many-one reduction from inequality problem to equality problem
Let the k-inequality-MIS problem be the decision problem whether an arbitrary graph $G=(V, E)$ contains a maximal independent set of at least size $k$, that is the corresponding language is:
$$\...
- 131
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