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
0
votes
0answers
35 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 ...
0
votes
1answer
53 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
32 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
49 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
38 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
108 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
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
40 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
20 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
28 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
42 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
64 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
51 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
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 ...
1
vote
1answer
125 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
37 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
48 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
54 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
304 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
1answer
55 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
281 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
158 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
87 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
19 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
677 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
47 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
34 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
1answer
335 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
84 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
68 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
1answer
58 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
36 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
50 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
366 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
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{...
2
votes
2answers
190 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
167 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
72 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
47 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
124 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 ...
0
votes
0answers
40 views

Finding the smallest-cost way to deliver goods

I want to deliver products from various sources to various destinations such that the overall cost is minimized. We need to deliver these products while obeying our contractual obligatione with each ...
3
votes
2answers
134 views

Playing video games to solve SAT instances

This paper shows that computer games, such as Super Mario, are NP-hard, by reduction from SAT. It may be possible to use this reduction to help solve hard instances of SAT: use the reduction to ...
3
votes
0answers
128 views

Reduction from 3-partition to ABC-partition

The ABC-partition problem is a variant of 3-partition in which, instead of a single set $S$ with $3 m$ positive integers, there are three sets $A, B, C$ with $m$ positive integers in each. The goal is ...
2
votes
0answers
95 views

3-partition problem without the restriction to triplets [closed]

In the standard 3-partition problem, there are $3 m$ integers, their sum is $m T$, and they have to be partitioned into $m$ subsets of sum $T$ and size $3$. Consider the variant without the ...
1
vote
0answers
16 views

Is there a fpt reduction of a NP-hard problem towards a fpt parameterisation $K'-D' \in FPT$?

Question While trying to search for a (example of a) NP-hard problem that fixed-parameter reduces to another NP-hard problem that is known to be fixed parameter tractable, such as k-Vertex Cover, my ...
1
vote
2answers
150 views

NP-completeness of a Generalized Version of Subset Sum

I am curious about the NP-completeness (or if not, an efficient algorithm) for the following generalization of the subset sum problem: In subset sum, we are given a number $t$ and a collection $S$ of ...
1
vote
1answer
123 views

Complexity of specific cases of MAX2SAT

I know that MAX2SAT is NP-complete in general but I'm wondering about if certain restricted cases are known to be in P. Certainly the languages $L_k:=\{ \phi \,|\, \phi\,\text{is an instance of 2SAT ...
0
votes
1answer
81 views

Can an NP-Complete problem be reduced to an NP problem?

All NP problems can be reduced to NP-Complete problems, can an NP-Complete problem be reduced to a NP problem (non complete)?
0
votes
0answers
35 views

$A \leq_p {\overline{A}} \Leftrightarrow {\overline{A}} \leq_p A$

I want to prove that $$A \leq_p {\overline{A}} \Leftrightarrow {\overline{A}} \leq_p A$$. Does anyone have a Idea how to solve this ?
2
votes
1answer
918 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 2
3
4 5
23