# 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].

943 questions
Filter by
Sorted by
Tagged with
20 views

### Weakest reduction for 3-$\mathrm{SAT}$

Having read all these posts Constant-depth threshold circuit for $\mathrm{PP}$ Is there any interesting consequence of $\mathrm{DLogTime}$-uniform ${\mathrm{Mod}_6}^0=\mathrm{NP}$ I wonder about ...
116 views

62 views

### Looking for a problem provably not in P

My basic position is that everything is in P. Then comes the time hierachy theorem and EXP. That's easy: simulate and then diagonalize. After that comes EXP-completeness; that's difficult to swallow. ...
274 views

### Is this problem NP-hard? Maximizing selected sets so that their union is less than k?

There is an NP-hard problem called Minimum k-Union where we are given a set system with $n$ sets and are asked to select $k$ sets in order to minimize the size of their union. I'm currently ...
56 views

### Understanding reductions for NP-completeness

Let's I have to make the following reduction: $$\text{CLIQUE}\le_p \text{VERTEX-COVER}$$ The technique of building the reduction is - Assume you can find a $\text{VERTEX-COVER}$ of size $k$, in ...
95 views

### Path in a vertex-weighted undirected graph

Is it an $NP$-hard problem? You're given an undirected graph $G(V,E)$ with vertex weight $w: V \to \mathbb{N}$ and a function $\mathrm{max}$-$\mathrm{visit}: V \to \mathbb{N}$ and a number $W$. Does ...
700 views

### PCP undecidability

There is a popular proof for the undecidability of the PCP (Post correspondence problem), which is outlined here: https://en.wikipedia.org/wiki/Post_correspondence_problem I'll assume whoever will ...
230 views

### Solve Hamilton Circuit with Hamilton Path

I want to show the reduction $HC \leq HP$. Let $G=(V,E)$ be my undirected graph. My idea is: For each edge $e=(u,v) \in E$ check whether $(V,E\backslash\{e\})$ has a Hamiltonian Path. If this is true ...
61 views

### If $L=\big\{\langle M_1,M_2\rangle\mid M_1, M_2\text{ are TM and } L(M_1)\cup L(M_1)=\Sigma^* \big\}$ is in $RE$ or $coRE$ or not in $RE\cup coRE$?

I tried to solve it as the following: $$\overline{L}=\big\{\langle M_1,M_2\rangle\mid M_1, M_2\text{ are TM and } L(M_1)\cup L(M_1)\neq\Sigma^* \big\}$$ I'll show that $\overline{L}\not\in RE$ by ...
57 views

### Finding reduction to prove that a language is NP-complete

I need to prove that the following problem is NP-complete: We have $n$ diplomats from $n$ countries and we need to seat them around a round table. We also get a list of diplomats who don't get along ...
39 views

181 views

### Prove that Weighted Independent Set is NP Complete using Independent Set?

$k$-Weight Independent Set Input: A vertex weighted graph $G=(V,E,w)$ and an integer $k$. Question: Is the a set $V'\subset V$ such that $V'$ is an independent set and $\sum_{v\in V'} w(v) \geq k$?...
185 views

### What does “AC0 many-one reduction” mean?

What does $\mathsf{AC^0}$ many-one reduction mean? I know about polynomial time reductions, but I'm not familiar with $\mathsf{AC^0}$ reductions.
36 views

### mapping reduction from $A_i=\{x|i \in W_x\}$ to $A_j=\{x|j \in W_x\}$

If $$A_n = \{ x | n \in W_x\} \ where \ W_x \ is \ domain \ of \ M_x$$ how can I show that $$\forall i,j \ \ \ A_i \le_M A_j$$
143 views

### Prove that the TM which would go over the leftmost position is not decidable

Let $M$ be a one-band TM and $w$ a word. We say that M tries to move the head over the left margin of the band if, while the head is in the leftmost position of $w$, the TM $M$ tries to move to the ...
86 views

### If A is reducible to B and B is reducible to A, and A is NPC, is B also NPC?

I was thinking about the max-clique problem and the k-independent set problem. You can show that k-independent set is reducible to max-clique easily and you can show that max-clique is reducible to k-...
142 views

### Do you have to do reduction both ways to prove a problem is NPC?

Also, what's the difference between transforming a problem into another problem and doing a reduction? They sound synonymous to me. Thank you!
50 views

226 views

### A TSP to HamCycle Reduction

I'm referring to the decision version of both $TSP$ and $HamCycle$. The first is, given a graph $G=(V,E)$, a weight function $w:E\rightarrow \mathbb R^+$ and an integer $k$, is there a simple cycle ...
33 views

### If a decision problem $A \in \text{NP}$ and there exists reduction so that $A \leq_p B$, for decision problem B, what can be deduced about B?

I think that it implies that B can be solved by a non-deterministic polynomial time or worse Turing machine, but I realise that there is possibly some greater result that I'm missing. Thanks in ...
209 views

### Is it NP hard to decide whether there exists a subset of V of size at most $k$ hitting all maximal bicliques of G?

The following problem is from my algorithms class: Given a graph $G(V, E)$, a set $C \subseteq V$ is called a biclique iff $G[C]$ is a complete bipartite graph, where $G(C)$ is the subgraph ...