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
16
votes
0
answers
167
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
12
votes
1
answer
422
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
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
-1
votes
1
answer
179
views
Will a non-linear lower bound on some NP complete problem prove non-linear lower bound on 3SAT?
A problem $\Pi$ is $\mathsf{NP}$ complete if there is a polynomial time reduction from an $\mathsf{NP}$ complete problem $\Pi^\circ$ to $\Pi$ with polynomial blow up on number of variables and ...
- 12.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 ...
- 18.9k
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
5
votes
1
answer
298
views
Reducing sorting to max-flow
Is there a linear-time reduction from the sorting problem to the max-flow problem?
If so, what would such a reduction look like?
- 53
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
0
votes
0
answers
93
views
Is this some variant of the Knapsack Problem?
We are a set of items $I = \{I_1, I_2,.. I_n\}$, which need to be placed in a certain number of knapsacks $K$. We can use as many knapsacks as we want and each knapsack has an infinite capacity but ...
- 101
2
votes
0
answers
133
views
Complexity of Knapsack-type problem with applications to computational workflows
Consider the following problem:
Let there be a set A of $n$ items $A=\{z_1, ..., z_n\}$, and let $W$ be a strictly positive integer. Each item $z_i$ has a value $v_i$ and a weight $w_i$. Finding a ...
- 87
4
votes
1
answer
607
views
#P- vs PP-Completeness
Suppose $A$ is any #P-complete problem. Now, $A$ is modified to obtain a decision problem $A'$ not by asking whether there is a solution but whether at least half of the potential solutions are ...
- 439
1
vote
0
answers
1k
views
Is there a reduction from a 0-1 knapsack problem to the unbounded problem?
As we know, an unbounded knapsack problem could be described as:
$\max \sum_{i=1}^nc_1x_i$
s.t. $\sum_{i=1}^na_ix_i\le b$
$x_i\ge0,x_i\in\mathbb Z,i=1,\cdots,n$
And for an 0-1 knapsack problem, we ...
- 11
6
votes
1
answer
158
views
Does learning conjunctions with malicious noise reduce to learning conjunctions with random noise?
In Feldman-Gopalan-Khot-Ponnuswami 06 the authors show that agnostically learning parities reduces to learning parities with random classification noise. They also remark (among other things) that ...
- 1,318
28
votes
1
answer
881
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
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
2
votes
0
answers
187
views
Introduction to Black-Box Separations in Cryptography
Are there any textbook-style material on black-box separations in cryptography? I tried to read the paper of Impagliazzo and Rudich but couldn't get much of it.
A previous StackExchange entry gives a ...
- 31
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
25
votes
5
answers
918
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
3
votes
1
answer
170
views
The relationship between completeness and strength of reductions
Ladner theorem can be stated as:
$P \ne NP$ if and only if there exists an incomplete set in $NP-P$.
Here an incomplete set is a set that is not complete for $NP$ under many-one polynomial time ...
- 20.8k
2
votes
2
answers
249
views
Balls & Bins: A punishment and reward game
Consider a game where one has a set of bins $(b_1, b_2, ...)$, and each bin has an associated initial count of balls $(c_1, c_2, ...)$. The rules of the game are as follows:
(1) Once a bin has a ...
- 23
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
1
vote
0
answers
87
views
Implication of lower bounds in Boolean circuit to other models of computation
Suppose that one can prove that some hard function $f$ with $n$ bit input does not admit any Boolean circuit of size at most $n^t$.
Then, how strong can we say about how hard $f$ is in other models? ...
- 1,130
8
votes
0
answers
720
views
Efficient Reduction from Min Cut to st-Min Cut
I am aware that many known algorithms for min cut problem is not by reducing the problem to $st$-min cut.
But the question of efficient reduction from min cut to $st$-min cut is still interesting to ...
- 1,130
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
3
votes
1
answer
277
views
Proof of an Ising model representation of graph isomorphism problem
I am going to through Ising formulations of many NP problems by Andrew Lucas. In section $9$ on page 22, the author introduced an exact Ising formulation of the graph isomorphism problem. Given two ...
- 653
6
votes
3
answers
260
views
Solving problems by deciding a logic
I am curious to know when open problems have been solved by expressing them in a specific logic, and then showing that this logic is decidable.
I have two distinct cases in mind:
The problem is ...
- 8,598
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") ...
- 36.9k
3
votes
2
answers
183
views
Root finding in [0,1]
I am interested in the problem of finding a real root of a polynomial equation $f(x)=0$ where
$f(x)=\sum_{i=0}^n a_ix^i$. Is it possible to give a reduction, i.e, to compute a different polynomial $g$ ...
- 181
2
votes
0
answers
178
views
Graph partition with objective over intra-partition weights
I have a problem in which I need to find an optimal graph cut that maximizes an objective over weights not on the cut. I have looked at the literature but have not been able to find any similar ...
- 21
0
votes
0
answers
38
views
On Equivalence of "gen-CONF" problem and "DH-exp-inv" problem
Let $g$ be a generator of a group of prime order $p$; $a,b ∈_R Z_p^+$
Consider an Algorithm $\mathcal{A}$ which on input $g,g^a,g^{ab}$ outputs $g^{br},r$, for some non zero $r ∈ Z_p$
And an ...
- 831
8
votes
1
answer
375
views
NP-hardness proof: looking for some good restricted np-hard problems
To show the NP-hardness of a problem, one need to choose a known NP-hard problem and find a polynomial reduction from the known problem to his problem in hand. Theoretically, any NP-hard problem can ...
- 463
14
votes
5
answers
737
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,393
3
votes
3
answers
168
views
On proving it is hard to compute $g^{rb}$ with knowledge of $r$, given $g, g^a, g^{ab}$
I am trying to prove the following
Given $g, g^a, g^{ab}$ it is hard to compute $r, g^r, g^{rb}$, for some arbitrarily chosen value of $r$
where $g ∈ \mathbb{G}, \mathbb{G}$ is a cyclic group of ...
- 831
8
votes
1
answer
969
views
Max-weight connected subgraph problem in planar graphs
The maximum-weight connected subgraph problem is as follows:
Input: a graph $G=(V,E)$ and a weight $w_i$ (possibly negative) for each vertex $i \in V$.
Output: a maximum-weight subset $S$ of vertices ...
- 1,166
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
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
9
votes
0
answers
261
views
A reduction between small cliques problems
I'm looking for a reduction that gets a graph $G=(V_G,E_G)$ and outputs a graph $H$ that satisfies the following requirements.
If $G$ contains a triangle, then $H$ contains a clique of size 9.
If $G$ ...
- 1,907
3
votes
1
answer
246
views
Maximize the expected number of "losers" - Is it NP-hard?
I am trying to find a reduction for a problem that seems NP-hard:
Let me start from a toy example. Consider 3 elements, $a$, $b$, and $c$.
You want to choose two pairs out of the three pairs and ...
- 33
4
votes
1
answer
617
views
On Random Self-reducible properties
Permanent is random self-reducible. $\mathsf{SAT}$ is not random self-reducible since otherwise the polynomial hierarchy collapses to $\mathsf{\Sigma_3}$.
1) Is $k$-sum random self-reducible?
That ...
- 12.8k
4
votes
1
answer
270
views
Permanent Approximation - Why can the JSV algorithm not handle matrices with negative entries?
Going through the literature, it seems that what it comes down to is that if one could efficiently approximate permanents of matrices with negative entries, then that would imply an efficient ...
- 143
-1
votes
1
answer
297
views
Graph Isomorphism: Polynomial time reduction from GI for disconnected graphs to GI for connected graphs? [closed]
Let the Graph Isomorphism Problem be the problem to decide whether there is a one-to-one mapping between the vertices of two graphs that preserves the edge relations.
Let the Graph Isomorphism ...
- 21
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
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
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 ...
- 21.5k
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.5k
4
votes
1
answer
250
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 ...
- 143
13
votes
1
answer
844
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 ...
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
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