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