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

Filter by
Sorted by
Tagged with
2
votes
1answer
132 views

Is the NP-hardness Proof with One Way Implication Correct and Why?

A problem $\Pi$ is NP-hard if I can prove this: a known NP-hard problem $\Pi'$ reduces to $\Pi$ in polynomial time; and $f(x) \in \Pi\iff$ $x \in \Pi'$. If I can show only one way implication, that ...
2
votes
1answer
237 views

Tight instance for unweighted maximum coverage problem?

The maximum (unweighted) coverage problem is defined as follows: Instance: A number $k$ and a collection of sets $S = \{S_1, S_2, \ldots, S_m\}$. Objective: Find a subset $S^{'} \subseteq S$ of sets, ...
2
votes
3answers
252 views

If P = NP, does SAT, or any other NP-Complete poly-reduce to any language different from $\emptyset$ or $\Sigma^*$?

I looked at Sipser ("Introduction to the Theory of Computation"), Problem 7.17: Prove that if P = NP, then every language in P, except $\emptyset$ and $\Sigma^*$, is NP-Complete. The solution is ...
2
votes
1answer
38 views

Can an alphabet be extended in a reduction proof? (with sample problem)

So I am working on solving a problem on whether following language is decideable: $L = \{n \in \mathbb{N} \mid M_n$ never freezes (for any input)$\}$, where $n$ is the Gödel-number of a Turing ...
2
votes
2answers
189 views

Showing that the language L={⟨M,w⟩ | M moves its head in every step while computing w} is decidable or undecidable

How would you go about showing that the language L={⟨M,w⟩ | M moves its head in every step while computing w} is decidable or undecidable? Intuitively speaking I think it is indeed undecidable because ...
2
votes
1answer
153 views

Reducing independent set to triangle-free subgraph

The INDEPENDENT-SET problem is a well-known NP complete problem that takes in a graph $G$ and an integer $k$. It returns true if $G$ has an independent set of size $k$. An instance of the TFS (...
1
vote
1answer
361 views

Show Resource Allocation Problem is NP-Complete

We are given $n$ tasks and $m$ resources. Each task $i$ requires a set $S_i$ of resources to be active, and each resource can be used by at most one task. The Resource Allocation problem asks: given $...
1
vote
1answer
330 views

Hamiltonian cycle, verifying and finding

If we have an algorithm that in polynomial time says if a graph G has an hamiltonian cycle, can we have an algorithm that in polynomial time find an hamiltonian cycle? My attempt is to delete an edge ...
1
vote
1answer
62 views

Turing machines: can a machine write to a finite number of memory cells, but not halt?

I am trying to reduce the Halting problem to show another problem is undecidable. The problem involves a program that is true if a machine $M$ writes to an arbitrary amount of memory, and false if it ...
1
vote
2answers
51 views

Reduction as a flowchart

I'm trying to understand the reduction as a flowchart graph. Let's say the boxes $A$ and $B$ are TMs/Functions and $x$ is the input. Is this plot represent reduction from $A$ to $B$ ($A\le B$) or ...
1
vote
1answer
447 views

Reduce ATM to REGULAR_TM

Consider $\mathsf{REGULAR_{TM}} = \{\langle M \rangle \mid \text{$M$ is a TM and $L(M)$ is a regular language}\}$. Let $S$ be the following algorithm, which solves $\mathsf{A_{TM}}$: “On input $\...
1
vote
1answer
59 views

Reductions where the number of certificates from one problem can be computed for another to varying degrees

Let $A$ and $B$ be two decision problems in $NP$. Consider three cases: (1) For any instance of problem $A$, one can produce, in polynomial time, an instance of problem $B$ having exactly the same ...
1
vote
1answer
128 views

Polynomial time reductions between two problems

I have two sets $A$ and $B$, I want to reduce $A$ to $B$ and $B$ to $A$. Formulas consist of a finite set of variables $\mathcal{V}$. An assignment $\sigma$ assigns truth values to each variable in $...
1
vote
0answers
342 views

Reducing a problem with two knapsack that needs equal number of items from Knapsack?

I am trying to reduce a Knapsack problem to a problem I need to solve, and I am suspicious of its NP-Completness. The problem recieve an array of elements $v_1,v_2,...,v_n$ sorted in some order from ...
1
vote
1answer
333 views

Reducing context-free languages with polynomial-time reductions

So, let's say we have two languages $L$ (which is any context-free language) and $M$ which is the basic CFL $\{0^n1^n: n\geq 0\}$. Can $L \le_p M$ ? Why or why not? How do polynomial time reductions ...
1
vote
1answer
584 views

Finding maximum-cardinality independent set with a particular oracle

We suppose we have a polynomial algorithm which receives a graph $G$ (any graph) and returns a stable set of $G, SA(G)$ with the following property: $\alpha(G) − |SA(G)| \leq k$ , for every natural $...
1
vote
1answer
1k views

Set cover problem and the existence of such cover

In the set cover problem we want to find in the $\mathbb{S} \subset 2^\mathbb{U}$ the subset $\{s_i\}_{1..k}$, such that $\cup s_i = \mathbb{U}$ for given $K$, where $k \le K$. But how to reduce the ...
1
vote
1answer
2k views

How to prove polynomial time equivalence?

Define the problem $W$: Input: A multi-set of numbers $S$, and a number $t$. Question: What is the smallest subset $s \subseteq S$ so that $\sum_{k \in s} k = t$, if there is one? (If not, ...
1
vote
1answer
783 views

How does this reduction to prove undecidability account for epsilon?

I have the following proof that the Empty String problem: ES = {M | M accepts $\epsilon$} is undecidable: $f<M,w>$ = Construct a new machine $M_2$ such that: $M_2$ = given input x erase x ...
1
vote
1answer
12k views

What does a polynomial time reduction mean?

I am having a little trouble understanding what is meant by a poly-time reduction. Suppose I have two algorithms $A$ and $B$ and then I say that $A$ is reducible to $B$. Does polytime reduction mean ...
1
vote
1answer
260 views

NP Complete Proof - Polynomial Reduction

We know that the INDEPENDENT-SET problem is NP Complete i.e $\langle G',k'\rangle$ means graph $G'$ has an Independent set of size $k'$. I am preparing for the finals an a sample question is to prove ...
1
vote
1answer
418 views

PSpace-completeness under PSpace reductions

A language $L$ is PSpace-complete, if it meets two conditions: It is in PSpace. Every other PSpace-complete language reduces to it in polynomial time. Question: suppose we change the second ...
1
vote
1answer
641 views

How is Vertex Cover reducable to Independent Set using parametrized reduction with parameter k?

We have the following Lemma and proof: Lemma 5.5. If $A$ if FPT, then $A\leq_{\mathrm{fpt}}$ Independent Set. Proof. We reduce $A$ to Independent Set parametrised by $k'$, where $k'$ is the size of a ...
0
votes
2answers
191 views

How is the Longest Path Problem NP complete?

From the following link: https://www.csie.ntu.edu.tw/~lyuu/complexity/2016/20161129s.pdf So basically, in our iff proof, we have to show two directions: Forward: If Hamiltonian Path has a yes-...
0
votes
1answer
2k views

Multiple-Choice Questions about decidability

I'm working on old MC-Questions about decidability und don't have the answers to the following ones: 1.) $L_1$ and $L_2$ are not decidable $\Rightarrow$ No superset of $L_1 \cup L_2$ is decidable 2.)...
0
votes
2answers
35 views

For every non-trivial language $A$ and every finite strict subset $B \subsetneq A$, it's holds that $A \le_m A \setminus B$

It's claim 1 from Bader Abu Radi's solution to this question. My solution (have no idea how wrong it is): $B$ finite $\Rightarrow$ $B\in R \Rightarrow$ exists TM $\langle M_B\rangle$ that halts $B$. *...
0
votes
1answer
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 ...
0
votes
0answers
96 views

A polynomial reduction from HAMPATH to LONG-PATH [duplicate]

$\text{HAMPATH} = \{(G=(V,E),s',t')| \text{ G has a Hamilton path from s' to t' } \}$ $\text{LONG-PATH} = \{(G,s,t,k) | \text{G has a simple path p from s to t, length(p) $\geq$ k} \}$ I'm trying ...
0
votes
1answer
22 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 ...
0
votes
1answer
115 views

Reduction — Do they work for unrelated problems?

I think I understand that a P class problem is reducible to an NP class problem (P≤NP). I´d like to understand if I need to figure out a potential algorithm which could solve the NP class problem to ...
0
votes
0answers
324 views

Turing machine M overwrites a non-blank char by B (Blank)?

What are the implications of a non-blank character being over-written by a Turing machine M for the given input variable 'x'? Intention of the question: I am trying to answer how the halting ...

1 2
3