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].
1,246
questions
1
vote
2
answers
112
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
1
answer
124
views
Show that both set A and set B are Turing reducible to some mixture of A and B
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 ...
- 39
0
votes
0
answers
57
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 ...
- 39
0
votes
1
answer
62
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 ...
- 123
0
votes
1
answer
61
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.
...
- 25
1
vote
2
answers
52
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.
- 13
-1
votes
1
answer
48
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),...
- 13
1
vote
0
answers
122
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(...
- 219
1
vote
1
answer
45
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 ...
- 319
1
vote
1
answer
34
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 (...
- 23
0
votes
1
answer
31
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 \...
- 165
0
votes
1
answer
128
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 ...
- 155
0
votes
1
answer
74
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?
- 373
3
votes
0
answers
57
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$, ...
- 31
0
votes
1
answer
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 ...
- 343
1
vote
1
answer
420
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 ...
- 343
0
votes
2
answers
44
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$.
*...
- 373
0
votes
1
answer
102
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 $\...
- 373
1
vote
2
answers
65
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 ...
- 373
2
votes
2
answers
408
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 ...
- 23
3
votes
1
answer
80
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
2
answers
450
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 ...
- 53
1
vote
1
answer
251
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 ...
- 11
3
votes
1
answer
179
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 ...
- 5,894
1
vote
0
answers
24
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 ...
- 111
1
vote
1
answer
1k
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 ...
- 131
0
votes
1
answer
69
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 ...
- 295
0
votes
1
answer
36
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
1
answer
768
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
1
vote
1
answer
180
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 ...
- 11
2
votes
0
answers
83
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 ...
- 121
0
votes
1
answer
66
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
1
vote
1
answer
62
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 ...
- 295
2
votes
1
answer
80
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
1
answer
821
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 ...
- 131
0
votes
0
answers
38
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,393
2
votes
2
answers
312
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 ...
- 818
0
votes
1
answer
184
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$...
- 100
0
votes
1
answer
297
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
1
answer
79
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 ...
- 393
1
vote
1
answer
318
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 ...
- 153
0
votes
0
answers
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 ...
- 1
3
votes
2
answers
189
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 ...
- 5,894
4
votes
0
answers
219
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 ...
- 5,894
2
votes
0
answers
110
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 ...
- 5,894
1
vote
0
answers
23
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 ...
- 123
1
vote
2
answers
235
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 ...
- 772
1
vote
1
answer
173
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 ...
- 1,601
0
votes
1
answer
166
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)?
- 39
0
votes
0
answers
39
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 ?
- 147