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
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 ...
Sean Kelly's user avatar
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 ...
Doc's user avatar
  • 140
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" ?
christianTuring's user avatar
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 ...
Mugen's user avatar
  • 121
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 ...
user3280193's user avatar
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 ...
Blunti's user avatar
  • 1
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 ...
advocateofnone's user avatar
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 ...
user2370336's user avatar
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&...
Daniel Stodůlka's user avatar
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$ ...
Moronic's user avatar
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 ...
letsBeePolite's user avatar
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 ...
Lee's user avatar
  • 217
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\...
ASDF's user avatar
  • 141
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 ...
D. Giver's user avatar
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 ...
RobotMan's user avatar
  • 161
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 ...
RunOrVeith's user avatar
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 ...
guest's user avatar
  • 11
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 ...
kitsuneFox's user avatar
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 ...
user1291235's user avatar
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 ...
JaSmin's user avatar
  • 1
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 ...
Hebi's user avatar
  • 51
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 ...
Carrey's user avatar
  • 1
-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)
Pratik Deoghare's user avatar
-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\,\,...
Ella 's user avatar
  • 109
-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 ...
Itay4's user avatar
  • 215
-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 ...
RandomGuy's user avatar
  • 111
-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 ...
PatrickBateman's user avatar
-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 ...
masterHaham's user avatar
-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?
gamma's user avatar
  • 115
-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 $...
Itamar Silverstein's user avatar
-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?
Hetzav Artax's user avatar
-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.
user3315748's user avatar
-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 “...
letsBeePolite's user avatar
-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)
Swathi's user avatar
  • 159
-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 ...
David2013's user avatar
-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 $...
S. M.'s user avatar
  • 317
-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 ...
hch's user avatar
  • 83
-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 $$
mmsamiei's user avatar
-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 ...
Yoni.A's user avatar
  • 9
-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 ...
Ricardo's user avatar
  • 105
-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 ...
Csfunda's user avatar
  • 11
-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 ...
ARK's user avatar
  • 169
-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 < ...
user6818's user avatar
  • 1,135
-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 ...
talon23's user avatar
-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 ...
Latif Salum's user avatar
-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 ...
kanpaitech's user avatar
-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 ...
user145121's user avatar
-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 ...
Matjaž's user avatar
-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} ...
pekusbill's user avatar
-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),...
hash man's user avatar