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
0answers
27 views

Proving B-Min-Cost Strongly connected Subgraph is NP-Complete

We have a strongly connected directed graph where each edge has positive integer weights. We are also given a $B \in \mathbb{N}$. Does there exist a strongly connected subgraph where sum of edge ...
2
votes
1answer
47 views

How is this reduction of 3-SAT to Half-SAT not valid? [duplicate]

I am studying algorithms and there is a question in CLRS called the Half-SAT problem We are given a 3-CNF formula with n variables and m clauses where m is even. We wish to determine whether there ...
1
vote
0answers
31 views

Polynomial variable of inapproximability after reduction

I proved the inapproximability of a problem that, given a multigraph $G = (V, E)$ and a set of vertices $U \subseteq V$ tries to maximize a score $f(U)$ whose value depends on the edges of the graph, ...
0
votes
1answer
28 views

Reduction from Clique to IS degree at most 4

This is from the Algorithms textbook by Dasgupta,C. H.Papadimitriou,andU. V. Vazirani question 8.6 (b) that asks: Edit: And missing from the pic as @Nathaniel points out in his answer below: "...
2
votes
1answer
15 views

Padding a 2SAT clause

In http://web.mit.edu/neboat/www/6.046-fa09/rec8.pdf, I see that they pad a 2SAT clause $(x\vee y)$ to make it a 3SAT clause by writing $(x\vee y\vee p) \wedge (x\vee y\vee \neg p)$. Why doesn't $(x\...
2
votes
1answer
72 views

How does strong NP-completeness agree with encoding complexity?

I've recently read about the concepts of weak and strong NP-completeness, but faced a problem in wrapping my head around them. I've understood that problems which have numerical parameters (like ...
1
vote
2answers
25 views

Reduction from Independent Set with fixed vertex to Independent Set

I was looking to solve this reduction, but I dont see how to construct the new graph. It seems very simple but I'm not capable of do it. I give you the complete explanation about this reduction. We ...
0
votes
1answer
14 views

Show that a set is turing reducible to another set

Consider an operator $+$ defined on $P(N)$ as follows: $A + B = \{2x\mid x \in A\}\cup \{2x + 1\mid x \in B\}$ Show that both $A$ and $B$ are Turing-reducible to $A+B$ I am kind of confused about this ...
0
votes
0answers
33 views

Show that a set is reducible to another set

Consider an operator $+$ defined on $P(\mathbb{N})$ as follows $$A + B = \{2x:\ x\in A\}\cup\{2x + 1:\ x\in B\}$$ Show that $A$ is $m$-reducible to $A+B$ and $B$ is $m$-reducible to $A+B$ As per the ...
1
vote
1answer
49 views

Any problem in P can be reduced to the language of odd integers

Given $A=\left\{n\in \mathbb{N} \mid \text{$n$ is odd}\right\}$, we want to prove that if $S \in P$ then there is a Karp reduction from $S$ to $A$. My attempt: If $S \in P$ we can solve $S$ with a ...
0
votes
1answer
20 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. ...
1
vote
2answers
41 views

If $f$ reduces $L_1$ to $L$ and also $L_2$ to $L$ is $L_1=L_2$

If the same $f$ reduces $L_1$ to $L$ and also $L_2$ to $L$ does it imply that $L_1=L_2$? My intuition says no, but I couldn't find a counterexample.
-1
votes
1answer
28 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
0answers
91 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(...
0
votes
0answers
19 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
35 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
18 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 (...
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 \...
0
votes
1answer
27 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 ...
0
votes
1answer
57 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?
3
votes
0answers
44 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$, ...
0
votes
1answer
34 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 ...
1
vote
1answer
62 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
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
38 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
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 ...
2
votes
2answers
155 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 ...
0
votes
0answers
23 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
49 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
202 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 ...
1
vote
1answer
114 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 ...
3
votes
1answer
73 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 ...
1
vote
0answers
17 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
188 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 ...
0
votes
1answer
35 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 ...
0
votes
1answer
26 views

Which of these properties hold for all FO theories? (but not regarding fragments thereof)

Which of these properties hold for all FO theories? (but not regarding fragments thereof) a. Decidable b. At least expressive as propositional logic c. NP-complete a) Decidable: no, some first order ...
0
votes
0answers
166 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 ...
1
vote
1answer
46 views

3Col reduction Variation, Special edges

I have a question concerning NP reduction. My question asks me to show that if I have a graph with Edges that connect 3 nodes together instead of 2, (Y style I assume). I need to prove that finding ...
2
votes
0answers
50 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
34 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
votes
1answer
54 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
35 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
1answer
133 views

Undecidability of closure under reverse of language accepted by TM

Prove that the following problem is undecidable using a reduction: Given a Turing machine $S$, does $S$ accept a word $w$ iff it accepts its reverse $w^R$? There is a solution here, which I don't ...
0
votes
0answers
36 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{...
2
votes
2answers
157 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
1answer
157 views

Reductions among two problems related to walks of length $k$

Consider the following two problems: A. Given a directed graph and a parameter $k$, determine if it contains a path (not necessarily simple) of length $k$. B. Given a directed graph, two vertices $s,t$...
0
votes
1answer
48 views

If two languages are decidable, can one be mapping reducible to the other?

If I have two decidable languages $A$ and $B$, is $A \leq_m B$ true? How would I show this?
2
votes
1answer
32 views

Why are $L$-reductions defined the way they are?

I was reading about $L$-reductions and there was one part in the definition that I thought was interesting. I wanted to know what motivated people who came up with it to have it included in the ...
1
vote
1answer
71 views

What is the polynomial time reduction between these two Hamiltonian cycle problems?

Problem 1: Given an undirected graph, return the edges of a Hamiltonian cycle, or correctly decide that the graph has no such cycle. Problem 2: Given an undirected graph, decide whether or not the ...

1
2 3 4 5
22