Questions tagged [reductions]
In computability and complexity, finding mappings between problems that allow solving one problem using a solution of another one. For reduction in programming language theory (e.g. beta-reduction), see [lambda-calculus] or [term-rewriting].
1,246
questions
3
votes
1
answer
329
views
Reduction of A_LBA to E_LBA
I have a rather interesting one to ponder and would love if I could get an answer for it. We were discussing the topic of mapping reduction today in my Computing theory course and I was wondering why ...
2
votes
1
answer
2k
views
Polynomial time reducibility
$L_1$ and $L_2$ are two languages defined on the alphabet $\sum$.
$L_1$ is reducible to $L_2$ in polynomial time. Which of the following
cannot be true?
$L_1 \in P$ and $L_2$ is finite
$...
- 529
29
votes
5
answers
57k
views
How can I reduce Subset Sum to Partition?
Maybe this is quite simple but I have some trouble to get this reduction. I want to reduce Subset Sum to Partition but at this time I don't see the relation!
Is it possible to reduce this problem ...
- 497
4
votes
2
answers
4k
views
Find an undecidable language that is mapping-reducible to its complement
As the title suggests. Also, such a language must satisfy that neither it nor its complement are semi-decidable. I already know that $All_{TM}, EQ_{TM}, T$ (that is the set of all deciders) satisfy ...
- 1,121
5
votes
1
answer
2k
views
Understanding the definition of reduction
From Wikipedia:
Given two subsets A and B of N and a set of functions F from N to N
which is closed under composition, A is called reducible to B under F
if $$
\exists f \in F \mbox{ . } \...
- 4,785
8
votes
1
answer
2k
views
Hardness and directions of reductions
Let us say we know that problem A is hard, then we reduce A to the unknown problem B to prove B is also hard.
As an example: we know 3-coloring is hard. Then we reduce 3-coloring to 4-coloring. By ...
- 1,783
17
votes
1
answer
3k
views
Planarity conditions for Planar 1-in-3 SAT
Planar 3SAT is NP-complete. A planar 3SAT instance is a 3SAT instance for which the graph built using the following rules is planar:
add a vertex for every $x_i$ and $\bar{x_i}$
add a vertex for ...
- 12.4k
31
votes
1
answer
7k
views
Sorting as a linear program
A surprising number of problems have fairly natural reductions to linear programming (LP). See Chapter 7 of [1] for examples such as network flows, bipartite matching, zero-sum games, shortest paths, ...
- 4,037
1
vote
0
answers
73
views
How to reduce MaxUNSAT to MaxSAT in a (almost) direct way?
In question How to reduce MaxUNSAT to MaxSAT? I was asking, how to reduce the MaxUNSAT problem to MaxSAT. With help of the given answer I could give a polynomial reduction : $MaxUNSAT \leq ...
- 249
2
votes
1
answer
308
views
How to reduce MaxUNSAT to MaxSAT?
Is it possible to reduce MaxUNSAT to MaxSAT in a polynomial way ?
When considering the MaxSAT problem, one often considers also the MinUNSAT problem, which is ...
- 249
9
votes
2
answers
5k
views
Infinite alphabet Turing Machine
Is a Turing Machine that is allowed to read and write symbols from an infinite alphabet more powerful than a regular TM (that is the only difference, the machine still has a finite number of states)?
...
- 298
12
votes
1
answer
10k
views
NP-complete proof from Dasgupta problem on Kite
I am trying to understand this problem from Algorithms. by S. Dasgupta, C.H. Papadimitriou, and U.V. Vazirani, chapter8, Pg281. Problem 8.19
A kite is a graph on an even number of vertices, say $2n$, ...
- 223
4
votes
2
answers
3k
views
How to reduce to an NP-hard problem?
For an assignment I have to program an application to schedule conversations.
There is an event where representatives of the elementary schools talks with the representatives of high schools. They ...
- 141
4
votes
2
answers
9k
views
Reduction from set cover problem to vertex cover problem
Although the reduction from vertex cover problem to set cover problem is quite simple, I did not find anywhere the reduction in the opposite direction. From the similarity in the type of problems, I ...
- 503
3
votes
0
answers
529
views
Hardness of counting solutions to NP-Complete problems, assuming a type of reduction
The $\text{NP-Complete}$ class of problems is defined w.r.t Karp Reductions, which are polytime many-one reductions. However, they need not necessarily preserve the number of solutions. A more ...
- 365
1
vote
1
answer
58
views
Produce decision version of the problem
An optimisation problem requires minimising some function $f(x)$, where $x$ is a
vector of integers. What is the corresponding decision version of the problem?
Princeps Tairu
15
votes
2
answers
3k
views
Types of reductions and associated definitions of hardness
Let A be reducible to B, i.e., $A \leq B$. Hence, the Turing machine accepting $A$ has access to an oracle for $B$. Let the Turing machine accepting $A$ be $M_{A}$ and the oracle for $B$ be $O_{B}$. ...
- 365
4
votes
1
answer
3k
views
Reducing TSP to HAM-CYCLE to VERTEX-COVER to CLIQUE to 3 CNF-SAT to SAT
In Cormen's Algorithms book on NP-completeness they prove various problems are NP-complete by reducing a previously proved NP-complete problem (call $K$) to current problem (call $L$). Each proof ...
- 309
9
votes
4
answers
5k
views
How are all NP Complete problems similar?
I'm reading few proofs which prove a given problem is NP complete. The proof technique has following steps.
Prove that current problem is NP, i.e., given a certificate, prove
that it can be verified ...
- 309
3
votes
1
answer
331
views
Can an exponential algorithm for an NPC problem be transformed into an algorithm for other NP problems in polynomial time?
After looking at other questions and my textbook, I seem to get some confusion.
I do get that when there is a polynomial algorithm of NPC, there is a polynomial algorithm for a NP problem.
But the ...
- 31
5
votes
0
answers
235
views
Find a permutation that maximize the minimum of $\frac{a_n}{a_{n-1}} + \frac{a_n}{a_{n+1}}$
Consider a sequence of $n$ positive real numbers $a_0,\ldots,a_{n-1}$. Let $S_n$ be the set of permutations on $\{0,\ldots,n-1\}$.
We are interested to find
$$
\max_{\pi\in S_n}\left( \min_{i=0}^{n-...
- 3,023
5
votes
2
answers
3k
views
Optimization problem vs decision problem - reduction
Assume we have an optimization problem with function $f$ to maximize.
Then, the corresponding decision problem 'Does there exist a solution with $f\ge k$ for a given $k$?' can easily be reduced to ...
- 249
2
votes
1
answer
1k
views
Showing that the set of TMs which visit the starting state twice on the empty input is undecidable
I'm trying to prove that
$L_1=\{\langle M\rangle \mid M \text{ is a Turing machine and visits } q_0 \text{ at least twice on } \varepsilon\} \notin R$.
I'm not sure whether to reduce the halting ...
- 511
5
votes
1
answer
6k
views
Is MAX-SAT NP-hard?
Is the MAX-SAT problem NP-hard? From the Wikipedia page:
The MAX-SAT problem is NP-hard, since its solution easily leads to the solution of the boolean satisfiability problem, which is NP-complete
...
- 249
19
votes
2
answers
2k
views
A polynomial reduction from any NP-complete problem to bounded PCP
Text books everywhere assume that the Bounded Post Correspondence Problem is NP-complete (no more than $N$ indexes allowed with repetitions). However, nowhere is one shown a simple (as in, something ...
- 193
6
votes
1
answer
375
views
What complexity class does this variation of traveling salesman problem belong to?
Given a TSP instance $T$, decide whether changing the city coordinates by adding a vector of coordinates $v$ will change the optimal TSP objective by atleast $x$. The city coordinates are integers.
...
- 61
7
votes
2
answers
1k
views
Is SAT in P if there are exponentially many clauses in the number of variables?
I define a long CNF to contain at least $2^\frac{n}{2}$ clauses, where $n$ is the number of its variables. Let $\text{Long-SAT}=\{\phi: \phi$ is a satisfiable long CNF formula$\}$.
I'd like to know ...
- 452
13
votes
2
answers
3k
views
Is Karp Reduction identical to Levin Reduction
Definition: Karp Reduction
A language $A$ is Karp reducible to a language $B$ if there is a polynomial-time computable function $f:\{0,1\}^*\rightarrow\{0,1\}^*$ such that for every $x$, $x\in A$ if ...
- 483
5
votes
1
answer
292
views
The $\text{k-key}$ problem
Given an undirected graph, I define a structure called k-key as a path containing $k$ vertices which are connected to a simple cycle which contains $k$ vertices as well.
Here's the k-key problem: ...
- 103
2
votes
1
answer
287
views
Does a collision oracle for the pigeonhole subset sum problem produce solutions?
I am reading "Efficient Cryptographic Schemes Provably as Secure as Subset Sum" by R. Impagliazzo and M. Naor (paper) and came across the following statement in the proof of Theorem 3.1 (pages 10-11):
...
- 829
0
votes
1
answer
2k
views
Solve a problem through reduction
I am aware that for a problem to be considered NP-Hard, any problem in NP must be reduceable to your problem (problem which you are trying to prove is NP-Hard).
Let's assume that you have proven that ...
- 17
4
votes
3
answers
597
views
Are there complete problems for P and NP under other kinds of reductions?
I know that the complexity class $\mathsf{P}$ has complete problems w.r.t. $\mathsf{NC}$ and $\mathsf{L}$ reductions.
Are these two classes the only possible classes of reductions under which $\...
- 441
7
votes
2
answers
14k
views
Reducing minimum vertex cover in a bipartite graph to maximum flow
Is it possible to show that the minimum vertex cover in a bipartite graph can be reduced to a maximum flow problem? Or to the minimum cut problem (then follow max-flow min-cut theorem, the claim holds)...
8
votes
2
answers
936
views
Complete Problems for $DSPACE(\log(n)^k)$
We know that the $polyL$-hierarchy doesn't have complete problems, as it would conflict with the space hierarchy theorem. But: Are there complete problems for each level of this hierarchy?
To be ...
- 1,368
14
votes
2
answers
615
views
Does every NP problem have a poly-sized ILP formulation?
Since Integer Linear Programming is NP-complete, there is a Karp reduction from any problem in NP to it. I thought this implied that there is always a polynomial-sized ILP formulation for any problem ...
- 253
10
votes
2
answers
5k
views
Mapping Reductions to Complement of A$_{TM}$
I have a general question about mapping reductions. I have seen several examples of reducing functions to $A_{TM}$
where $A_{TM} = \{\langle M, w \rangle : \text{ For } M \text{ is a turing machine ...
- 203
9
votes
3
answers
2k
views
Turing reducibility implies mapping reducibility
The question is whether the following statement is true or false:
$A \leq_T B \implies A \leq_m B$
I know that if $A \leq_T B$ then there is an oracle which can decide A relative to B. I know that ...
- 511
11
votes
2
answers
10k
views
If A is mapping reducible to B then the complement of A is mapping reducible to the complement of B
I'm studying for my final in theory of computation, and I'm struggling with the proper way of answering whether this statement is true of false.
By the definition of $\leq_m$ we can construct the ...
- 511
14
votes
1
answer
687
views
Direct reduction from $st\text{-}non\text{-}connectivity$ to $st\text{-}connectivity$
We know that $st\text{-}non\text{-}connectivity$ is in $\mathsf{NL}$ by Immerman–Szelepcsényi theorem theorem and since $st\text{-}connectivity$ is $\mathsf{NL\text{-}hard}$ therefore $st\text{-}non\...
- 21.9k
2
votes
3
answers
2k
views
Finding the flaw in a reduction from Hamiltonian cycle to Hamiltonian cycle on bipartitie graphs
I'm trying to solve a problem for class that is stated like so:
A bipartite graph is an undirected graph in which every cycle has even
length. We attempt to show that the Hamiltonian cycle (a ...
thomascirca
37
votes
2
answers
17k
views
How do I construct reductions between problems to prove a problem is NP-complete?
I am taking a complexity course and I am having trouble with coming up with reductions between NPC problems. How can I find reductions between problems? Is there a general trick that I can use? How ...
- 371
22
votes
3
answers
15k
views
HALF CLIQUE - NP Complete Problem
Let me start off by noting this is a homework problem, please provide only advice and related observations, NO DIRECT ANSWERS please. With that said, here is the problem I am looking at:
Let HALF-...
- 1,115
1
vote
3
answers
2k
views
Subset-sum and 3SAT
Two things (this may be naive):
Does anyone believe there is a sub-exponential time algorithm for the Subset-sum problem? It seems obvious to me that you would have to look through all possible ...
- 171
6
votes
1
answer
2k
views
Reducing directed hamiltonian cycle to graph coloring
The 3-SAT problem can be reduced to both the graph coloring and the directed hamiltonian cycle problem, but is there any chain of reductions which reduce directed hamiltonian cycle to graph coloring ...
- 163
14
votes
2
answers
3k
views
Reduction from 3-Partition problem to Balanced Partition problem
The 3-Partition problem asks whether a set of $3n$ integers can be partitioned into $n$ sets of three integers such that each set sums up to some given integer $B$. The Balanced Partition problem asks ...
- 4,387
6
votes
1
answer
816
views
Reduction to equipartition problem from the partition problem?
Equipartition Problem:
Instance: $2n$ positive integers $x_1,\dots,x_{2n}$ such that their sum is even. Let $B$ denote half their sum, so that $\sum x_{i} = 2B$.
Query: Is there a subset $I \...
- 61