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
1
vote
3answers
458 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
24 views

Find a Cook Reduction from $R_{Clique}$ to its determinist problem

The question is to find Find a Cook Reduction from $R_{k-Clique}$ to its determinist problem. Basically: k-Clique: a group of $k$ nodes in the graph such there is an edge between every two nodes. ...
0
votes
1answer
29 views

reduction of independence problem and cluster problem

independent problem is: there is a simple and undirected graph, we are looking for the maximum vertex in which there is no edge between any two of them. cluster problem is: there is a simple and ...
-1
votes
1answer
34 views

Reduction from $VC$ to $CD$

We define the vertex cover as the problem of finding for a graph $G$, a cover of size $k$. A cover is a set of vertices such that every vertex has an edge to this set. We define CD (cycles destructor),...
1
vote
1answer
134 views

Problem with proving that $RP \subseteq NP$ : a non-deterministic TM for a language $L \in RP$

I'm having a small issue with wikipedia's proof that $RP \subseteq NP$: An alternative characterization of RP that is sometimes easier to use is the set of problems recognizable by nondeterministic ...
2
votes
1answer
672 views

Is protein folding really NP-hard and how to show that?

This question has two facets that are related. Is the general problem of protein folding really NP-hard? The hydrophobic-polar protein folding model (Ken Dill et al., 1985) stated the problem on a ...
1
vote
0answers
100 views

Reduction between Parity-SAT and approximate counting

Consider two problems as defined here. Approximate counting: Given a Boolean function $f(x)$, for $x \in \{0, 1\}^{n}$, distinguish between the two cases: The number of satisfying assignments for $f(...
4
votes
2answers
430 views

Polynomial-time linear-reduction from Directed Hamiltonian Path Problem to 3SAT

Is there a polynomial-time reduction from Directed Hamiltonian Path Problem to 3SAT which is linear in the number of vertices? That is, it reduces every directed graph $G$ with $n$ vertices to a ...
0
votes
0answers
20 views

Does having a similar constraint while reducing a problem to similar problem to prove np hard means they are same?

I have been trying to find the computational complexity of my optimization problem and found that it is Np-Hard. To prove it to Np-Hard, I try reducing it Nurse Scheduling Problem. I am quite confused ...
1
vote
1answer
39 views

A question about domains in Karp reductions

A basic question or request for clarification regarding Karp reducibility: Let $\Sigma^*$ be the set of all finite strings of 0's and 1's. Call a subset of $\Sigma^*$ a language. Let $\Pi$ denote ...
1
vote
1answer
19 views

Circuits and Closure Under Reductions

Suppose that $A$ and $B$ are languages such that $A\leq_P B$ (many-to-one Karp reduction), and $B\in \mathbf{P/poly}$. How do we prove that $A\in\mathbf{P/poly}$? Using similar ideas like Cook-Levin (...
1
vote
1answer
418 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 ...
5
votes
2answers
1k views

Transforming SAT to Quadratic Programming in polynomial time

I would like to show that Quadratic Programming is NP-hard. I am currently reading a couple of papers which state that QP is NP-Hard and prove it by transforming SAT to QP, however I am finding the ...
3
votes
0answers
47 views

Sufficient condition for a complexity class's closure under NP-reductions?

Let us say that there exists a $\mathsf{NP}$-reduction from a problem $A$ to another problem $B$ when there exists a non-deterministic, polynomial-time Turing machine $T$ such that for each $a \in A$, ...
1
vote
1answer
125 views

NPC-problem reduction to triangle-free 3-colorability

lately, I have encountered a problem that I struggle to find a satisfactory solution for. I need to prove that triangle-free 3-colorability is NP-complete. Therefore I assume the right way is to find ...
0
votes
1answer
26 views

Condition to prove $f$ is a reduction

A theorem says if $f$ is a computable function and we can prove $x \in A \Leftrightarrow f(x) \in B$, then we can use reduction so $A \leq_m B$. But i'm confused if should I prove if : $(x \in A \...
2
votes
1answer
62 views

If well-founded induction holds, then the relation $\to$ on a reduction system terminates

I am trying to understand a proof from "Term Rewriting and All That" by Baader and Nipkow. Well-founded induction (WFI) is the following statement: $\forall x \in A(\forall y \in A(x \...
0
votes
1answer
60 views

Cook–Levin theorem and reduction as injective function

I saw that the injectivity "derives directly from the theorem", but i can't see how it's happen, any explanation?
0
votes
1answer
33 views

Reducing the Hamiltonian cycle to the travelling salesman problem and self loops

If this is my adjacency matrix for the hamiltonian cycle: $$\begin{pmatrix}0&1&0&1\\ 1&0&1&0\\ 0&1&0&1\\ 1&0&1&0\end{pmatrix}$$ Then a reduction ...
1
vote
3answers
9k views

reduction from SET-COVER to VERTEX-COVER

I've come with an idea for reduction from the set-cover problem to the vertex-cover problem, But I'm not sure if this reduction is correct. I saw in this post's comments that "There cannot be a nice ...
8
votes
3answers
3k views

Solving the min edge cover using the maximum matching algorithm

To solve an instance of an edge cover, we can use the maximum matching algorithm. Edge Cover: an edge cover of a graph is a set of edges such that every vertex of the graph is incident to at least one ...
0
votes
1answer
39 views

If$A \leq_T B$ is given, can you reduce $\overline{A}$ to $B$ and vice-versa

If you are given two languages $A$, $B$ and $$A \leq_T B.$$ Is it possible to $\overline{A} \leq_T B$ or $A \leq_T \overline{B}$? Here is my shot. Case 1: $\overline{A} \leq_T B$ This is only possible ...
0
votes
2answers
36 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$. *...
1
vote
1answer
96 views

Can you reduce every decidable language to a regular language?

One of my previous questions on an exam was the following Can you reduce a decidable language to a given regular language? (decidable language $\leq _m$ regular language). If so, does this mean that ...
0
votes
1answer
41 views

Reduction from $A$ to $B$ as execution of Turing machines

As explained in answers to this question, reduction from $A \le B$ can be represented in the following way. But in this example: from here At least as I understand it: The reduction is from $\...
1
vote
2answers
53 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 ...
2
votes
2answers
241 views

Proving decidability

Regarding the following languages $L_1$ and $L_2$, I want to prove that $L_1$ is decidable and $L_2$ is undecidable. I want to construct a turing machine which can decide $L_1$ and reduce the halting ...
3
votes
2answers
7k views

Showing that deciding whether a given TM accepts a word of length 5 is undecidable

I'm having trouble grasping this the concept of reductions. I found the solution and it looks like this: Assume that $M_5$ is a Turing Machine that can decide if a given Turing Machine $M$ accepts ...
0
votes
0answers
27 views

Reducing co-NP and NP. (Karp and Turing)

Why is it true that: If every problem in co-NP can be Karp reduced to a problem A, every problem in NP can be Turing reduced to A?
3
votes
1answer
50 views

surprizing reducibility and challenge on it

Assume that Problem $A$ is polynomial-time reducible to problem $B$. Claim 1: If problem $A$ is NP-hard then problem $B$ is NP-hard. Claim 2: If problem $B$ is NP-hard then problem $A$ is NP-hard. ...
2
votes
2answers
260 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 ...
3
votes
1answer
78 views

If a solution to Partition is known to exist, can it be found in polynomial time?

In the Partition problem, there is a set of integers, and the goal is to decide whether it can be partitioned into two sets of equal sum. This problem is known to be NP-complete. Suppose we are given ...
7
votes
3answers
1k views

Simple proof for NP-completeness of Edge Dominating Set

In a graph, an edge dominating set is a subset D of the edges such that any edge in the graph is either in D, or shares an endpoint with an edge in D. The Minimum Edge Dominating Set problem is to ...
1
vote
1answer
204 views

Prove a TM problem is NP-complete

Question: Show that $T_{NP}$ is NP-complete, where $$T_{NP} = \{m\#w\#^c\mid M_m\text{ is an NTM};M_m(w)\text{ has an accepting computation of $\leq$ c steps}\}$$ This question looks weird to me ...
1
vote
0answers
18 views

Time-Sensitive Reductions for Undecidable Problems

I'm studying Comparability and Complexity, and through the course, a number of problems (namely, the halting problem for Turing Machines, etc.) have been proven undecidable through elementary proofs ...
1
vote
1answer
325 views

Show linear bounded automata accepting w is PSPACE-complete

ALBA={⟨M;w⟩ | M is linear bounded automata which accepts input w} Show that ALBA is PSPACE-complete. How I would try to solve it... We need to prove ALBA belongs ...
3
votes
1answer
1k views

How to reduce INDEPENDENT SET to INDEPENDENT SET SIZE?

Suppose you are given a polynomial-time algorithm for the following problem related to INDEPENDENT SET: INDEPENDENT SET VALUE Input: An undirected graph G. Output:The size of the largest ...
0
votes
1answer
36 views

Show that if the discrete log problem is $(T,1-\epsilon)$-hard, then it's $(O(\frac{T}{\frac{1}{\epsilon}log\frac{1}{\epsilon}}-nlogm),\epsilon)$-hard

Show that if the discrete log problem is $(T,1-\epsilon)$-hard, then it's $(O(\frac{T}{\frac{1}{\epsilon}log\frac{1}{\epsilon}}-nlogm),\epsilon)$-hard Let $G$ be a cyclic group of size $m$, and let $g ...
2
votes
2answers
171 views

how does Kleene-Post show two languages that are not Turing reducible to each other?

I'm having difficulty understanding the proof of the Kleene-Post result. It purports to construct two languages that are not Turing reducible to each other, using a diagonalization argument. I've seen ...
0
votes
0answers
252 views

reduction from ALLTM to ETM

I am trying to understand why this "proof" of ETM undecidability is wrong. ALLTM={ < M >|M is a TM, L(M)=∑*} ETM={< M >|M is a TM, L(M)=∅} We know that ALLTM is undecidable, lets ...
2
votes
0answers
60 views

Why do I only need to reduce from one problem in NP to prove NP-Hardness?

Suppose I wish to show that my decision problem $Q$ is NP-Hard. Why do I need to reduce from one problem $Q'$ of known hardness ? Consider for instance the following situation: Here, I have my set NP ...
0
votes
0answers
41 views

$P$-Complete proof

I need to solve the next problem: Consider the language: $$\operatorname{LIN\mbox{−}PROG} = \left\{(A, b)\bigg|\begin{gather} \exists\in\mathbb{R}^n\ Ax\leq b\text{ where }A\in\mathbb{R}^{m\times n}\ ...
1
vote
1answer
259 views

Why log-space reduction is used for NL-completeness while PSPACE reduction isn't used for PSPACE completeness?

NL-Complete languages are defined by Log-space reduction, while PSPACE complete languages are defined by poly-time many-to-one reduction. According to these posts : Why not polynomial-space reductions ...
0
votes
1answer
56 views

If A is not in NP, and A reduces to B, does this mean B is not in NP?

I know it is true that if A is not in P, and A reduces B, then B is not in P. But is it true for NP as well? If A is not in NP, and A reduces to B, does this mean B is not in NP? Why or why not? ...
1
vote
1answer
33 views

Check if a linear function or an affine function can be a pseudo random function

Let $G = \{0, \cdots , p-1 \}$ be a field. Let $K = G^{m \times n}$ and $F:K \times G^n \to G^m$ be a family of functions. For $A \in G^{m \times n}$ and $x \in G^n$ we have $F(A,x) = Ax$. I need to ...
2
votes
0answers
41 views

Proving that DCONN is NL-Complete

I am having trouble with some homework regarding proving that DCONN is NL-Complete. As part of the exercise, the fact that RCH is NL-Complete can be assumed. Problem definitions: RCH: Given a ...
0
votes
2answers
1k views

How to reduce from subset-sum problem?

I have this problem which is described as follows: Input: You are given a multi-set $M$ (a set that can contain duplicates), and two numbers $P$ and $T$. $M = {(x_1,y_1), (x_2,y_2), ..., (x_n,...
3
votes
2answers
605 views

Example of two undecidable languages that cannot be mapping reduced to each other

I want to find two undecidable languages $A$ and $B$ that $A$ cannot mapping (i.e. many-one) reduce to $B$, $B$ cannot reduce to $A$. One of my thought is to let $A$ be the halting problem, let $B$ be ...
2
votes
2answers
544 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!
0
votes
0answers
37 views

Are all reductions from NP-complete problems either NP-complete or are contained in P?

Let's say we have a problem $A \in \mathsf{NP}$. Now let's say we have a reduction $f(\mathsf{SAT}): A \leq \mathsf {SAT}$. So, assuming that $A$ is not $\mathsf{NP}$-complete we have that $f(\mathsf{...

1 2
3
4 5
23