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,280
questions
0
votes
0
answers
33
views
Proving NP-Complete Help [duplicate]
I am trying to prove that the problem of having a person at the minimum x number of intersections to be able to see each street is NP-Complete. I think that the street problem is very similar to the ...
0
votes
0
answers
18
views
Is NP-complete complexity defined in terms of polynomial reductions or polynomial transformations? [duplicate]
How do you know that a decision problem $X$ is NP-complete?, if all other NP-problems polynomially transform to $X$ or if all other NP-problems polynomially reduces (there exist a polynomial time ...
0
votes
0
answers
58
views
Polynomial Reduction and P [duplicate]
Why w ∈ A if and only if f(w) ∈ B ? Which the signification of "if and only if" ?
0
votes
0
answers
231
views
Are there any RE-complete languages w.r.t. polynomial reduction?
I need to decide if there exists $L\in RE$ so that for every $L'\in RE$ we have $L' \leqslant_p L $, meaning a polynomial-time reduction.
I've tried to use $L=A_{TM}$ (the accepting problem), but got ...
0
votes
0
answers
1k
views
Max Flow / Linear Programming Reduction Variant
While studying max flow / LP, I came across a couple of reduction problems that gave me a bit of pause:
Here are two variants of the standard Maximum Flow problem. Show that both of them can be ...
0
votes
0
answers
216
views
Trying to show if two languages are recognizable or not
I have two languages that I am trying to prove are recognizable or not:
Let $$L_1 = \{(\langle M\rangle, w) \mid \text{$M$ is a TM that accepts $w$ and doesn't accept $\varepsilon$}\}$$ where TM is ...
0
votes
0
answers
31
views
Is there a general form of polynomial reductions in complexity theory? [duplicate]
While reading Sipser, in computability I read about many to one mapping reducibility and Turing reducibility,the latter one being a more general form of reducibility. But in the introductory chapter ...
0
votes
0
answers
177
views
Reduction from 3-Partition to a cutting problem
My problem is the following:
Input: a set of $m$ non-negative integers $\{b_1,...,b_m\}$ and a parameter $n$ with $n<m$.
Output: $n$ sets of 3 numbers
Task: Cut the $b_i$'s into $3n$ integers such ...
0
votes
0
answers
906
views
Reducing the halting problem to the uniform halting problem
As stated here https://books.google.cz/books?id=dwpeNRgjK68C&pg=PA57&lpg=PA57&dq=uniform+halting+problem&source=bl&ots=qsbv_672W9&sig=NDcebhxrwcYdF-P15dor565l8Jc&hl=en&...
0
votes
0
answers
59
views
Is NP-hardness closed?
Let $X\leq Y$.
If $X$ is $NP$-hard, is $Y$ $NP$-hard? I think yes, as if an $NP$ problem is reducible to $X$ in polynomial time, then surely it is also reducible to $Y$ given that $X\leq Y$.
If $Y$ ...
0
votes
0
answers
423
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 ...
0
votes
0
answers
80
views
mapping reduction for every recursive language [duplicate]
how do I prove that for every 2 languages $A,B\in R$ where $A,B \notin \{ \emptyset , \Sigma^* \}$
I can do a reduction $A \leq_m B$?
[EDIT]
My try:
$A$ is decidable therefore it has a turing ...
0
votes
0
answers
96
views
Reducing a Knapsack-type problem to a known problem
The Quadratic Knapsack problem, introduced by Gallo, is an optimization problem in the following form:
$max \sum_{i=1}^n{\sum_{j=1}^n{q_{ij}x_ix_j}}$
$s.t \sum_{i=1}^n{w_ix_i} \leq c$
$x \in \{0, 1\...
0
votes
1
answer
113
views
Validity of reduction (3-SAT)
I'm trying to show that a special variant of the common 3-SAT is NP-complete by reducing 3-SAT to this special variant.
This special variant works like the normal 3CNF-SAT, except every other clause ...
0
votes
0
answers
389
views
Is it decidable whether a TM accepts more than one word? [duplicate]
Is the following language:
$\qquad\displaystyle L= \{\langle M\rangle \mid M \text{ is a TM }, |L(M)|>1\}$
Turing-decidable?
I think it isn't, because if a Turing machine T can decide L, then T ...
0
votes
0
answers
299
views
Reduction of specific scheduling problem to show np-completeness
Given a Set K of n tasks, a set T of t possible time-intervalls to schedule any task, and a number k:
Is there a schedule for the tasks, such that there are at most k conflicts (time - overlaps) of ...
0
votes
0
answers
50
views
Request for help with two reductions
Given two graphs one needs to decide if one of them has a subgraph isomorphic to the other.
Given a subset of a graph one needs to decide if the induced subgraph is triangle free.
Can someone ...
0
votes
0
answers
135
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
1
answer
2k
views
Reduction from partition to multiprocessor scheduling
I am kind of unsure about a reduction between two problems.
Here are the two problems:
PARTITION:
Instance: A finite set of n positive integers $S= \{a_1,a_2,...a_n\}$.
Question: Can the set $S$ be ...
0
votes
0
answers
159
views
Reduction CVP to CFG problem
I want to show that non-emptiness of context free language is P-complete. So, I am trying to reduce CVP to this problem by generating grammar from circuit. I consider all type of gates in circuit and ...
0
votes
0
answers
295
views
Hamiltonian path in dynamic graph
Given an undirected Graph. I want to find a hamiltonian path with no restriction to starting or ending vertices. I know there are some smart algorithms for solving that.
Now let's make things ...
0
votes
2
answers
114
views
Is a language semi-decidable iff it is reducible to ATM?
Thank you. I see how it makes sense going in the opposite direction but i need help proving that this is true.
Below is the definition of ATM.
ATM={<M,w>| a TM, M accepts w}
The question from my ...
-1
votes
1
answer
612
views
Why does reduction from vertex cover to subset sum use base-4? [closed]
Why does reduction from vertex cover to subset sum use base-4?
30.13 Subset Sum (from Vertex Cover)
-1
votes
2
answers
342
views
size of intersection of 2 languages size is not decidable
I think that the next language is not decidable but I can't think of reduction to show it.
I would appreciate some hint or intuition
$EQ = $ { $<M1,M2>$ |$ M1\,\,\, and\,\,\, M2 \,\,\, are\,\,...
-1
votes
1
answer
76
views
Prove/Disprove: If $A _{\leq M} B$ and $B _{\leq M} A$ then $A=B$
Given $A, B$ languages over $\Sigma,$ Prove/Disprove: If $A _{\leq M} B$ and $B _{\leq M} A$ then $A=B$.
I would like to disprove this claim, with the languages $H_{TM}$ and $H_\epsilon = \{\langle ...
-1
votes
1
answer
61
views
SAT reduction to prove NP completeness [closed]
Suppose you have a set of binary strings of length n, the magnitude of a string is the number of 1's it has. and you want the program to return true if there is a string of length n that has a ...
-1
votes
1
answer
48
views
if there is a 3/2 approximation algorithm for independent set then there is a 3/2 approximation algorithm for vertex cover?
if by absurdly there is a 3/2-approximation algorithm for INDIPENDENT SET then does there exist a 3/2-approximation algorithm for VERTEX COVER?
the implication should be true because independent is ...
-1
votes
1
answer
164
views
Reduction from problem A to another problem B
I have a question from a test that I failed to pass, I failed to do the question.
The question:
Let A and B have two languages so that there is a reduction function f: $A\leq _pB$.
Suppose that $A \in ...
-1
votes
1
answer
34
views
If a problem C is NP hard and there is an existing reduction from/to A,B,D, are they NP hard as well?
Lets say there is an reduction in polynomial time from problem A to B, from problem B to C and from problem C to D. Now lets say C is NP hard. Does this mean A,B,D are NP hard as well?
-1
votes
1
answer
490
views
Can Atm language be reduced?
I'm familiar with reductions to the language $A_{\mathrm{TM}}=\{\langle M,w\rangle | M \text{ accepts } w \}$, for example $A_{\mathrm{TM}}\le H_{\mathrm{TM}}$.
Are there examples for reductions from $...
-1
votes
1
answer
237
views
How to polynomially reduce euclidean tsp to regular tsp?
The normal tsp seems way harder than the euclidean one, is the euclidean tsp np complete? If so is there a simple reduction that gives an answer to the tsp if you have the euclidean tsp algorithm?
-1
votes
1
answer
211
views
Is A mapping reducible to B if B = A?
Is A mapping reducible to B if B = A?
Let's say A is undecidable but Turing-recognizable and also Turing reducible to its complement.
-1
votes
1
answer
615
views
Reduction from 3SAT [closed]
You are given a directed acyclic graph G = (V, E) in which each node has one
“left” out-arc and one “right” out-arc, with a distinguished source node s and sink node t. You are also given a list of “...
-1
votes
1
answer
31
views
polynomial time reduction of 2 langauges
If we can reduce a language y to x.
x ≤P y
how do I prove
x(complement) ≤P y (complement)
-1
votes
1
answer
442
views
Properties of polynomial time many-one reductions
I'm working on old multiple choice exams and would like to know if the following statements are true or false:
a) $L_1 \le_p L_2 \le_p L_3 \Rightarrow L_1 \le_p L_3$
b) If $L \in \mathsf{NP}$ and $U ...
-1
votes
1
answer
136
views
Reduction of RE and Rec languages
Suppose $L_1$ is reduces to $L_2$ in polynomial time, $L_1\leq_p^\mathsf{}L_2.$ we know that if $L_2$ is RE then $L_1$ is also RE and $L_2$ is REC then $L_1$ is also REC.
And also I know that if $...
-1
votes
1
answer
323
views
Reduction from SAT to 3SAT
a few days ago I had a test and could not pass it. This is a question I did not understand in the test.
Recall the reduction we saw $SAT \leq _p 3SAT$. Given verse $\varphi$ in the form of $CNF$, we ...
-1
votes
1
answer
39
views
mapping reduction from $A_i=\{x|i \in W_x\}$ to $A_j=\{x|j \in W_x\}$
If $$ A_n = \{ x | n \in W_x\} \ where \ W_x \ is \ domain \ of \ M_x $$
how can I show that
$$ \forall i,j \ \ \ A_i \le_M A_j $$
-1
votes
1
answer
273
views
Poly-time reduction from HAMPATH to HAMPATH-E
I need to prove that
HAMPATH-e = { < G,s,t,e > | G is directed graph, s, t are vertices and e a edge }
there is hamiltonian path between s to t that cross the edge e
is an NP complete.
i've ...
-1
votes
1
answer
574
views
Languages reducible to and from context-free
Let $L'$ be a context-free language. If $L \leq_M L' \leq_M L''$, where $\leq_M$ denotes mapping reducibility (aka many-one reducibility), what can we know about $L$ and $L''$?
I think they're both ...
-1
votes
1
answer
51
views
many one reduable [closed]
I A many one reducable to B and given A is decidable then is B decidable ?
preparing for an exam and please let me know if this holds
I understood how if B is decidable then A is decidable
and if A ...
-1
votes
1
answer
162
views
All but Five Three Colorable
An NP Problem Named All But Five Three Colorable(AB53C) is defined as follows :- Input : Connected Graph G(V,E) The Connected Graph is AB53C, iff the Given Graph is 3-Colorable by leaving UPTO 5 ...
-1
votes
1
answer
7k
views
How to reduce bin-packing problems? [duplicate]
This is my first time with reductions and I can't figure out how to do them. I have read the few standard examples that are given in the standard books.
For example, given $n$ numbers $\{ 0 < ...
-1
votes
1
answer
99
views
Understanding reductions and notation
I am currently working through Sipser's Introduction to the Theory of Computation. In chapter 5, he defines that a Language $A$ is mapping reducible to language $B$, written $A\leq_m B$ if there is a ...
-1
votes
1
answer
35
views
A sufficient condition for unsatisfiability
Let $\varphi = \bigwedge C_k$, in which $C_k$ is a clause in X3SAT (exactly-one 3SAT or one-in-three 3SAT). That is, $C_k = (l_i \odot l_j \odot l_u)$ such that $l_i \in \{x_i, \overline{x}_i\}$ for ...
-1
votes
1
answer
62
views
Showing NP-completeness of a graph problem with vertex capacities
The problem:
Given an undirected graph G = {V, E}, a source-vertex s, and each vertex having a "capacity" between 0 and |V|, is there a tree which covers all vertices and does not extend ...
-1
votes
1
answer
34
views
If two languages are polytime reducable, does that imply they are also turing reducable
Is it possible for a pair of languages where A ≤T B but not A ≤p B?
I am not sure if this could be the case since a turning reduction would imply we can use a decider for one language to decide ...
-1
votes
1
answer
408
views
NP Reduction - Dominating set to SAT
Given a graph G and an integer k , recognize whether G contains dominating set X with no more than k vertices. And that is by finding a propositional formula ϕG,k that is only satisfiable if and only ...
-1
votes
1
answer
50
views
Are the following assertions true if P != NP?
We consider the NP-complete $CLIQUE$ problem. Let furthermore $MST^*$ be the minimum spanning tree problem. Assume that $P \ne NP$ and explain whether the following assertions hold:
$MST^* \le_{P} ...
-1
votes
1
answer
51
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),...