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.
210
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,668
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
1k
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.4k
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,868
32
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,798
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,843
28
votes
1
answer
886
views
Are there subexponential algorithms for PLANAR SAT known?
Some NP-hard problems which are exponential on general
graphs are subexponential on planar graphs because the
treewidth is at most $4.9 \sqrt{|V(G)|}$ and they are exponential
in the treewidth.
...
- 1,955
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,832
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
25
votes
5
answers
920
views
Curious about computer-assisted NP-completeness proofs
In the paper "THE COMPLEXITY OF SATISFIABILITY PROBLEMS" by Thomas J. Schaefer, the author has mentioned that
...
- 2,329
24
votes
2
answers
975
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
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 ...
22
votes
5
answers
34k
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
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,902
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.8k
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 ...
- 19k
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
17
votes
2
answers
752
views
Is intersection of $k \ge 3$ graphic matroids in P?
It is known that intersection of three general matroids is NP-hard (source), which is done via reduction from Hamiltonian cycle. The reduction uses one graphic matroid and two connectivity matroids.
...
- 173
16
votes
2
answers
882
views
Does Karp reducibility yield a total order?
Or with other words, do we have that for every language $A$ and $B$, $A \leq_p B$ or $B \leq_p A$?
- 355
16
votes
3
answers
419
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
16
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,...,...
- 325
16
votes
0
answers
169
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
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 ...
15
votes
1
answer
536
views
Sampling a uniformly random satisfying assignment
Problem: Given $\phi : \{0,1\}^n \to \{0,1\}$ represented by a boolean circuit, generate a uniformly random $x \in \{0,1\}^n$ such that $\phi(x)=1$ (or output $\perp$ if no such $x$ exists).
Clearly ...
- 2,803
15
votes
1
answer
472
views
Validity of exponentiation in a polynomial time reduction
I asked this question 10 days ago on cs.stackexchange here but I didn'y have any answer.
In a very famous paper (in the networking community), Wang & Crowcroft present some $\mathsf{NP}$-...
- 1,138
15
votes
1
answer
265
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 ...
- 21.6k
15
votes
1
answer
952
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,806
14
votes
5
answers
738
views
Should reductions make us more or less optimistic for the tractability of a problem?
It seems to me that most complexity theorists generally believe the following philosophical rule:
If we can't figure out an efficient algorithm for problem $A$, and we can reduce problem $A$ to ...
- 2,403
14
votes
1
answer
858
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 ...
14
votes
0
answers
474
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
13
votes
3
answers
345
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 ...
- 19k
13
votes
2
answers
1k
views
Is ALogTime != PH hard to prove (and unknown)?
Lance Fortnow recently claimed that proving L != NP should be easier than proving P != NP:
Separate NP from Logarithmic space. I gave four approaches in a pre-blog 2001 survey on diagonalization ...
- 3,043
13
votes
1
answer
845
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 ...
- 606
13
votes
1
answer
3k
views
Improving Cook's generic reduction for Clique to SAT?
I am interested in reducing $k$-Clique to SAT without making the instance much larger.
Clique is in NP so it can be reduced to SAT using logarithmic space.
The straightforward Garey/Johnson textbook ...
- 19k
13
votes
2
answers
616
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
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&...
12
votes
1
answer
212
views
Reductions between languages of different densities?
The density of a language $X$ is a function $d_X \colon \mathbb{N} \to \mathbb{N}$ defined as $$d_X(n) = |\{x\in X \mid |x| \le n\}|.$$
Suppose $A$ and $B$ are languages over some finite alphabet, $A$ ...
- 19k
12
votes
1
answer
423
views
Which complexity class does this number theory problem belong to?
'Given $a,b,c\in\Bbb N$, is there $x,y\in\Bbb N$, $ax^2+by=c$' is $\mathsf{NP}$-complete.
Which complexity class does 'Given $a,b,c\in\Bbb N$, is there $x,y\in\Bbb N$, $ax^2+by^2=c$' belong to?
user34945
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
12
votes
1
answer
295
views
Slowest many-one reduction?
When we want to prove that an $L\in \bf NP$ is $\bf NP$-complete, then the standard approach is to exhibit a polynomial time computable many-one reduction of a known $\bf NP$-complete problem to $L$. ...
- 11.4k
12
votes
0
answers
394
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,550
12
votes
3
answers
342
views
Is there a reduction to "door and pressure plate" games that doesn't explode solution length?
This paper gives a proof that in a game with doors and pressure plates, it is PSPACE-hard to determine whether or not the (player's) avatar can reach a given location. This is proven by a reduction ...
user6973
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,763
11
votes
4
answers
907
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.4k
11
votes
5
answers
908
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
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,041
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
11
votes
3
answers
320
views
Calculus of Constructions: compress expression to its smallest form
I'm aware that the Calculus of Constructions is strongly normalizing, meaning every expression has a normal for that cannot be beta,eta-reduced further. So in fact this is the most efficient ...
- 213
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
1
answer
839
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