Stack Exchange Network

Stack Exchange network consists of 174 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange

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].

0
votes
0answers
10 views

Reducing weighted linear threshold gate to unweighted one

Reading "On the power of threshold circuits with small weights" by Siu and Bruck I have faced several problems understanding how unweighted linear threshold element can be built efficiently from the ...
1
vote
0answers
16 views

If problem A is logspace reducible to 2-SAT, is A in NL?

I'm trying to prove that some problem, A, is in NL. I have found a logspace reduction from A to 2-SAT - am right in thinking that this is not sufficient to prove that A is in NL? If so, how does one ...
1
vote
1answer
9 views

Reducing optimization problem to its decision version

There are two problems that need to be solved. Both problems use a compatibility matrix $C$, where $C[a, b]$ is how compatible students $a$ and $b$ are. (1) Given an $n \times n$ compatibility matrix ...
1
vote
0answers
22 views

Is the solution to Independent Set or Vertex Cover from 3-SAT optimum?

There are plenty of resources online discussing 3-SAT reductions to Independent Set or Vertex Cover problem. I am unable to find a resource which states that a satisfiable assignment to 3-SAT results ...
2
votes
2answers
34 views

Can a RE language be reduced to a non-RE language?

In our lecture notes about many-one reduction we showed that the following statements hold: $$ L, L' \subseteq \mathbb{N}\space and \space L\leq L'$$ $$(I)\space L' \in RE \implies L\in RE$$ $$(II)\...
1
vote
0answers
18 views

Is there a relationship between time taken to reduce A to B and the time taken to solve B?

Example: If it takes $O(n^2)$ to solve A and it takes $O(n^3)$ to reduce A to B. So, it is certain that that B is at least as hard as A and takes at least $O(n^2)$ time to be solved. Can we say ...
2
votes
2answers
36 views

Given that A reduces to B in $O(n^2)$ and B is solvable in $O(n^3)$, solve A

Suppose a problem A reduce to problem B and reduction is done in $O(n^2)$ time. If problem B is solved in $O(n^3)$ time then what about the time complexity of problem A? Approach: A is reduced ...
0
votes
0answers
21 views

Reduce 3-Coloring to 3-Coloring with minimum vertex degree 4

Is there any way to reduce the 3-Coloring graph problem to a 3-Coloring problem with the condition of every vertex must have at least 4 degree? If such reduction exists, what could be an appropriate ...
-3
votes
0answers
28 views

reduction from dominating set to dominating value [closed]

Give a reduction from dominating set (DomSet) to dominating value (DomVal): DomVal = {(G,p)| G is an undirected graph with V’⊆V and val_G(V’)≥p} where val_G is the number of dominated vertices not in ...
2
votes
1answer
41 views

Are you allowed to change the specifications of a problem when doing reductions?

I'm doing a polynomial time reduction from problem A (known graph problem) to problem B (funky and specific longest path problem). There is a lot of demands on how problem B is supposed to be solved. ...
0
votes
0answers
11 views

Proof that a language is not r.e. via reduction [duplicate]

I have to proof that the following language: L:={ DTM | DTM halts for an infinite amount of inputs } is not recursively enumerable. Intuitively, I'd pick the ...
1
vote
1answer
26 views

Reduce ATM to the language of TM encodings where if the TM accepts w then the TM accepts ww

Today I did a test in my class, the trace was: Prove that the language $L =\{\langle M\rangle\mid \forall w \in \{0,1\}^\ast: M \text{ accepts }w\implies M \text { accepts }ww \}$, is undecidable ...
2
votes
1answer
115 views

Directed HAM Cycles with Additional Constraints to SAT

The $n$ dimensional hypercube $Q_n$ is a graph that has a vertex $v_s$ for each string $s \in \{0, 1\}^n$ and an edge between two vertices $v_s$ and $v_t$ if and only if the Hamming distance between $...
2
votes
1answer
36 views

Example for an undecidable language L such that L is reducible to its complement and vice versa

I am searching for an undecidable language $L$, such that $L \leq \Sigma^* \setminus L$ and $\Sigma^* \setminus L \leq L$, but I am not able to find a concrete language and reduction. Is there ...
1
vote
1answer
78 views

Proving problem NP-completeness [duplicate]

I am studying computational complexity and i am trying to solve this problem. We are given a (non-bipartite) complete graph: G = (V, W, E) where the vertices can be divided in two classes V and W ...
0
votes
1answer
29 views

Prove that $L = \{a^i \;:\; (\exists x \in \mathrm{Lang}(M_i))\;[ xx \notin \mathrm{Lang}(M_i) ] \}$ not recursively enumerable [duplicate]

Past year paper question: Let $M_i$ denote the Turing machine with code $i$ using the alphabet $\Sigma=\{a,b\}$. Show that the following language is not recursively enumerable: $L = \{a^i \;:\; (\...
0
votes
0answers
126 views

Reduction from membership problem

i'm preparing for my exam from Formal languages and automata and i've found one example, which i don't know, how to deal with it. I've a language A with some rules and i need to prove using reduction ...
1
vote
1answer
15 views

NP-Completeness reduction, using a same input

We have problem X and Y that we know is NP-Complete. Problem X uses graph G as an input and Problem Y uses graph G and constant k as an input. Problem we are trying to reduce to, which I will call Z, ...
1
vote
1answer
23 views

reducing a decision problem to a local search problem

Lemma 4 in How easy is local search by Johnson, Papadimitriou, and Yannakakis, states: If a PLS problem is NP-hard then NP = P So assuming L is a PLS problem (polynomial local search problem) that ...
0
votes
0answers
17 views

Modelling the following Entscheidungsproblem as the flow network problem

We have sensors that collect data and send them from time to time as packet to a center node in the network.We want to study if we can achieve that in T steps.So let´s consider a graph G=(V,E) a ...
0
votes
0answers
25 views

Does the reduction of a language to another with a bijective function imply that they are equally solvable?

I understand that if $A \leq B$ and $A$ is not a recursively enumerable set then $B$ is also not a recursively enumerable set. (and if $A \leq B$ and $B$ is decidable then $A$ is decidable) What if ...
2
votes
1answer
41 views

Decidability of Turing Machine accepting exactly 14 words

Would you say that the following problem is undecidable? $$L_1 = \{\langle T \rangle \mid T \text { accepts 14 words}\}$$ My intuition says that this must be undecidable, and I want to try to reduce ...
0
votes
1answer
78 views

How can I show that a problem is not $NP$

Consider the following image: The problem is: can we cover the bigger rectangle with small rectangles such that no two rectangles overlap and no gap opens up? Prove that this problem is $NP-Hard$. I ...
0
votes
0answers
25 views

How to prove that this TSP variation is NP-Hard?

The problem is as follows: given a list of cities, a list of distances between them, and upper bounds for date/times that the cities must have been visited by, compute the shortest (optimal) going ...
1
vote
2answers
82 views

If P = NP, can all NP problems be solved within time $O(n^k)$ for fixed $k$?

I came across this question while studying for an exam: T/F: Suppose we can show for some fixed $k$, an NP-complete problem P has a time $O(n^k)$ algorithm. Then every problem in NP has a $O(n^k)$ ...
2
votes
0answers
43 views

Reducing a problem to 2-SAT

Given a matrix $A$ with entries $a_{ij} \in \{0,1\}$, the matrix $B$ is formed by $b_{ij}=a_{ij} + a_{i+1,j} + a_{i,j+1} + a_{i+1,j+1}$. $B$ has one row and one column less than $A$. The problem is ...
1
vote
1answer
38 views

Proof By Contradiction - Hamiltonian Paths and Cycles

Was hoping if anyone had any way to prove the following claim using proof by contradiction Let $G = (V, E)$ be a simple graph with at least one vertex, and let $G'$ be the graph formed by adding a ...
-1
votes
2answers
83 views

Reduce EXACT 3-SET COVER to a Crossword Puzzle

I have an assignment where I have to prove that solving a crossword puzzle is an $NP$-complete problem by reducing from EXACT 3-SET COVER. I have more or less given up at this point and if anyone ...
1
vote
1answer
19 views

Many-One Reducibility of decision problems for complexity theory?

A many-one reduction of problem $A$ to problem $B$ is essentially a function that converts a problem instance in problem $A$ to an instance in $B$. This allows you to use a $B-$solver one time to ...
0
votes
0answers
38 views

Relation relationship between two given problems and Subset Sum

$$\begin{align*} L&=\Big\{(a_1,...,a_{2n},k) : k,a_i \in \mathbb N ,\exists S \subset (a_1,...,a_{2n}) \text{ s.t. } |S|=n \text{ and } \sum_{a_i\in S} a_i =k\Big\}\\ L'&=\Big\{ (a_1,...,a_{...
1
vote
1answer
29 views

findMax reduce to sort

Can I reduce the find max (or find min) problem to the sort problem? Because if so, knowing the lower bound for find max is Ω(n) I can also infer that the lower bound for sorting is Ω(n) too? I'm ...
0
votes
0answers
28 views

size of the maximum independent set

The Independent-Set problem takes a graph $G = (V,E)$ and an integer $k$ and asks if $G$ contains an independent set of size $k$. (An independent set is a set of vertices such that no pair of vertices ...
-1
votes
1answer
40 views

is This reduction possible?

If we have $L \in p$ and $L' \neq \emptyset$ and , $L' \neq \Sigma^*$ . is $L \leq^p L' $ ? I read this question Reduction between $\Sigma^*$ and $\emptyset$ Maybe this question is irrelevant to my ...
2
votes
2answers
186 views

Prove: Every decidable set is Turing reducible to the empty set

Question- Prove: Every decidable set is Turing reducible to the empty set. Can anyone help me with this please? All reductions tutorials I've seen use practical examples of reduction such as sipser'...
1
vote
1answer
213 views

How to prove the following: Every set is Turing reducible to itself

Question: Prove the following: Every set is Turing reducible to itself. If anyone can provide a solution that would be great, I've just been introduced to computation theory so be as descriptive as ...
2
votes
1answer
43 views

Decidability of equivalence of two context free grammars

I got a question regarding the decidability of equivalence of two context free grammars: Construct a Turing machine that decides whether $L(G) = L(H)$, where $G$ and $H$ are two context free ...
0
votes
0answers
19 views

Dimensionality Reduction to Find Abstract Concepts

I have a list of say 1000 topics and each are related to computer programming field such as if/else topic, while loop , for loop, integers, strings ect. I want to create a concept map for them which ...
2
votes
1answer
49 views

How to reduce a problem?

I am a bit confused on how to reduce a problem. I'll give an example: Let's say there is a problem called HALTEMPTY and we know it is undecidable. $HALTEMPTY_{TM} = \{\langle M\rangle \mid M \text{ ...
1
vote
1answer
43 views

Prove if a property of a Turing Machine is decidable or not, how can I do it?

I cannot understand how to prove if a certain property of a Turing Machine M is decidable or not. For example, if a have this: (1.1) "M always halts within 100 steps" or this (1.2) "M recognizes ...
0
votes
1answer
35 views

On the proof of NP-Hardness of the Cardinality Constrained Quadratic Knapsack Problem

in Polyhedral Study of the Cardinality Constrained Knapsack Problem the authors prove that the Cardinality Constrained Knapsack Problem is NP-Hard by reducing PARTITION to it. Besides, it's easy to ...
0
votes
1answer
57 views

Existence of polynomial time reduction from P to R?

Why the next idea doesn't work: If L_2 in R and L_1 in P and the languages are not trivial, then there is a polynomial-time reduction from L_1 to L_2 I know ...
1
vote
2answers
58 views

How to define (logically) the complement language?

I found it a little bit difficult and confusing to define the complement language in specific cases. For example, take the next language: $$L = \left\{\langle M, w\rangle \;\middle|\; \begin{array}{...
1
vote
1answer
25 views

Is Rectilinear Steiner Tree still NP-complete when points have integral coordinates?

Garey proved that the Rectilinear Steiner Tree problem is (strongly) NP-hard. I wonder if it is still true when we retrict the points to have integral coordinates and lie on a square of side lenght n^...
0
votes
1answer
75 views

Alternate reduction from 3SAT to 4SAT?

It seems that the standard reduction method you see online from 3SAT to 4SAT is that we let $\phi = (a \lor b \lor c)$ be a 3SAT clause, and so there is an assignment that satisfies $\phi$ iff $\phi' =...
3
votes
2answers
35 views

Question about mapping reducibility

I am working on an assignment where one of the sub questions is: Let $A$ and $B$ be languages. Suppose $A$ is context free and $A ≤_m B$, which means that there is a computable function $f\colon \...
0
votes
1answer
19 views

Weakest reduction for 3-$\mathrm{SAT}$

Having read all these posts Constant-depth threshold circuit for $\mathrm{PP}$ Is there any interesting consequence of $\mathrm{DLogTime}$-uniform ${\mathrm{Mod}_6}^0=\mathrm{NP}$ I wonder about ...
3
votes
1answer
75 views

$TSAT$ is $NP$-complete

In "Computational Complexity" by Arora and Barak they state that the following is $NP$-complete: $\{ \langle \alpha, x, 1^n , 1^t \rangle : \exists u \in \{0,1\}^n \text{ s.t. } M_{\alpha} \text{ ...
0
votes
3answers
27 views

Collection of meta-reductions in theory of $\mathrm{NP}$-completeness

I want to start a wiki post about meta-result of meta-reductions in the theory of $\mathrm{NP}$-completeness. This can be regarded as a reference request post. Any links are appreciated. At least, ...
0
votes
1answer
25 views

Is this reduction from 3D-MATCHING to PATH SELECTION invalid?

I'm a bit confused about some proof that PATH-SELECTION-PROBLEM is NP-complete (Problem 9, chapter 8 in "Algorithm Design" by Tardos and Kleinberg) that I found in some solution manual here: https:...
0
votes
1answer
28 views

Cook completeness of a variant of Vertex Cover

Is this variant of Vertex Cover Cook-complete for $\mathrm{NP}$? Input: An undirected graph $G(V, E)$ together with a vertex cover $C\subseteq V$ Output: YES if there exists a vertex cover $C'\...