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,284 questions
Filter by
Sorted by
Tagged with
51 views

if there is a 3/2 approximation algorithm for independent set then there is a 3/2 approximation algorithm for vertex cover?

if by absurdly there is a 3/2-approximation algorithm for INDIPENDENT SET then does there exist a 3/2-approximation algorithm for VERTEX COVER? the implication should be true because independent is ...
53 views

Reduction from a language with unknown decidability to HALT

We were taught to use reductions in order to show that a given L is undecidable. My question is, given some definition of a new L, is there a way to find a reduction $$L\leq_mHALT$$ So that I can ...
• 1
60 views

112 views

Do all NP-hard problems have a reduction from one to another (Either A $\leq_m$ B or B $\leq_m$ A)

Given two problems, $A$ and $B$, that are NP-hard. Is either one of the following is true? $A \leq_m$ B $B \leq_m$ A In other words, is there always a relationship between any two arbitrary NP-hard ...
• 327
187 views

Sorting Numbers in O(N)?

Why is sorting numbers Omega(nlogn)? I'm thinking of an reduction algorithm where: For all the numbers x_i, we create a point (x_i, 0) on a 2d graph. Fit a line directly to the right starting from ...
64 views

Is finding a Polytime reduction from $L_1$ to $L_2$ equivalent to proving $L_2 \in P \Rightarrow L_1 \in P$

I often hear NP-completeness as problems such that, if they were in $P$ all problems in $NP$ are in $P$. The true definition, though, is that NP-complete is a set of languages in NP that all languages ...
• 153
43 views

Do reductions (in NP and other classes) follow a linear path?

NP has several complete problems, which reduce to one another. In this sense, they are all "equal" in terms of hardness. There are other problems in NP that are also "equal" to one ...
• 243
34 views

Reduction between problems where problem A solves problem B with probability $\frac{2}{3}$

Suppose we have a problem, $A$, and a machine $T_A$ that solves $A$. Now, let's say we have a problem $B$ that is solvable with a polynomial number of calls to $T_A$, and we call $T_B$ the machine ...
• 243
102 views

• 2,982
1 vote
33 views

• 125
1 vote
71 views

$L=\{<M>|M~is~a~TM~and~L(M)=\{0^n1^n|n\ge0\}\}$

About the language $L=\{<M>|M~is~a~TM~and~L(M)=\{0^n1^n|n\ge0\}\}$ I want to determine if it is in RE / coRE or neither. I think that I found a mapping reduction from $\overline{A_{TM}}$ to $L$, ...
• 47
1 vote
34 views

Reducing problems to solve easier problems

Is there any instance where a problem $A$ can be reduced to a problem $B$ where $B$ is easier to solve than $A$? I've been learning about NP-Hardness recently and seems that the answer is no. Whenever ...
• 113
20 views

To Prove NP-Completeness [duplicate]

Given a Directed Graph G, and some subsets of vertices T1,T2,..Tn(These subset can intersect) , is there a path in this graph such that it is acyclic and contains exactly 3 vertices from each Ti. I'm ...
• 1
1 vote
195 views

Show problem is NP-hard

I'm preparing for my exam and I got stuck on the following problem: The gardening problem: We have access to a set of different types of seeds and a number of plant pots.For each plant pot, there is ...
• 21
1 vote
54 views

Mapping reduction - Bit Flip

Let $L=\{<M> | M$ is a TM, $L(M)\ne \emptyset$ and $\forall x\in L(M), \overline{x} \notin L(M) \}$ While $\overline{x}$ is the bit flip of $x$. I want to show a mapping reduction to prove that ...
• 47
375 views

Reduction from SUBSET SUM to COIN CHANGING

The COIN-CHANGING problem is NP-complete, but I am having difficulty finding a proof for its NP-hardness in the form of a reduction from another NP-complete problem ...
1 vote
36 views

Choosing the ideal problem to prove the hardness

I am research scholar currently working in complexity theory. Recently, i have started working on hard proofs and reductions. It is very well established that there is a polynomial reduction from ...
169 views

NP-hard $k$-SAT variant with exactly $\ell$ occurrences per variable

For the purpose of this post, let $k$-SAT be SAT with exactly $k$ literals per clause, as opposed to the more common meaning of at most $k$ literals per clause. With the purpose of proving some ...
• 807
45 views

NP-hard (3-)SAT variant with $n$ clauses and $f(n)$ variables

With the purpose of proving my problem NP-hard, I'd like to reduce from a SAT variant (which of course should remain NP-hard) in which not two parameters are present (typically $n$ clauses and $m$ ...
• 807
1 vote
236 views

Graph Isomorphism Problem: decisional vs functional

The Graph Isomorphism Problem is a classic in Computer Science. In its decision version $(DGI)$, we are given two graphs $G$ and $H$ and we are asked if there exists an isomorphism between the two. In ...
27 views

Assume we know that (1) $A$ reduces to $B$ in time $O(f(n))$ time and (2) $B$ reduces to $A$. What can we say about the time for $B$ -> $A$?

The question is basically the title. If two NP-Complete problems reduce to each other, do we know that the reductions take equal amounts of time? What about space? Does this apply for all 'invertible' ...
82 views

Show this 2D Grid Set Cover-ish problem is NP-Complete?

Given a $n \times m$ rectangular grid of cells each with an integral weight: $w_{i,j}$ and two integer parameters $w \ge 2$ and $h \ge 2$ (for group width and height respectively). Select the subset ...
• 313
1 vote
48 views

show for any Languages $L_1$ and $L_2$ exists a Language $L$ with $L_1 \leq_{log} L$ and $L_2 \leq_{log} L$

This is an old exam question, but I never found a solution or somebody who could explain it to me. Here is the problem statement: Let $\Sigma$ be an alphabet with |$\Sigma$| $\geq 2$. Show that for ...
• 23
Can fine-grained hardness be proved directly from classical hardness (e.g., $\sf P \neq NP$) in some way?
I have just learnt about some typical result of fine-grained hardness in 15-455 by Prof Ryan: CNF-SETH implies ${\sf DIAMETER} \notin {\sf TIME}(mn^{1-\epsilon})$. (Here DIAMETER stands for the graph ...