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

1
vote
2answers
24 views

NP-hardness does not imply lower bound, strictly speaking?

A problem is NP-hard iff every NP problem can be polynomially-time reduced to it. Hardness is often intuitively explained as a lower bound. But it isn't, strictly ...
-1
votes
0answers
56 views

Undecidability of the “Single-Halting Problem”

I have to show for a turing machine S that is taking another TM T and a word x as input and only halt for one specific T and x, that it is not decidable. The idea is now to reduce it to the halting ...
2
votes
1answer
64 views

Max flow and Matching problem

Where can i find a list of problems reducible to max flow and matching problems. I need such examples to learn and practice .
1
vote
1answer
15 views

Expecation of $u'^t v$ = $u^t v$

I have another question with dimensionality reduction. I have a matrix $S \in R^{k \times d}$ and S is in {$- \frac{1}{\sqrt k}, \frac{1}{\sqrt k}$} and i have two vector $u,v \in R^d $. I need to ...
2
votes
1answer
46 views

Confusion about proof of undecidability of REGULAR TM in Sipser's book

in the book "Introduction to the Theory of Computation" by Michael Sipser there is an example of undecidable languages in which there is a language REGULR_TM which is described as follows : ...
2
votes
0answers
30 views

Is the language $L$ of coded CFG's Turing decidable?

Consider the following language $L$ = {$<G><w>$ | $G$ is a CFG and $w\in L(G)$} Now, I wish to prove that $L$ is Turing decidable. My gut tells me to construct a Turing machine that ...
0
votes
0answers
18 views

Finding if a given problem is a Np-Hard problem - recruitment problem

I have to prove that the following Recruiting problem a NPC-problem. Input: n candidates and m positions and a matrix A $\in {Q^{n\times n}}$. Each entry $A_{ij}$ with i < j tells how much gets ...
0
votes
2answers
74 views

Which of the following statements are true for the given special cases of the Traveling Salesman Problem?

I'm taking the Algorithms: Design and Analysis II class, one of the questions asks: Which of the following statements is true? Consider a TSP instance in which every edge cost is either 1 ...
1
vote
1answer
31 views

How to prove that a problem is undecidable by using the Halting problem?

I cannot understand how to reduce the halting problem to a property to show that is undecidable. For example, I have this property of a Turing Machine and I have to prove if it's recursive or not: "...
1
vote
0answers
26 views

RO turing machine with finite memory

Consider the following: A weak TM is a TM with finite tape in size $k$ which can only read its input values. note: the tape size does not include the input length. I need to determine whether if the ...
-1
votes
0answers
31 views

Polynomial reduction from HCP to SAT [closed]

I have searched if there exists code in Java that make polynomial reduction of Hamiltonian cycle problem to SAT, but I have not found any. How I can find that polynomial reduction? Can you give me the ...
3
votes
1answer
422 views

So if a problem is more difficult the language it represents is smaller?

I'm reading the definition of polynomial time reducible: Let $L_1, L_2$ be two language. If $L_1$ is polynomial time reducible to $L_2$ then exists $f:\{0,1\}^*$ s.t. $\forall x\in\{0,1\}^*$ $$x\in ...
0
votes
1answer
22 views

Show that $A_\mathrm{LBA}$ is PSPACE-Complete?

I want to show that $A_\mathrm{LBA}$ is PSPACE-Compelte. Say we proved it is in PSPACE. Now for PSPACE-HARD: I had an idea, which was very similar to some solution i found on the web- say we have a ...
1
vote
1answer
45 views

Reducing subset sum to even subset sum

I'm trying to learn reduction. I have this problem called "even subset sum" that's very similar to subset sum. It's the same problem as as subset sum except that the only numbers allowed are even ...
1
vote
0answers
16 views

Why is the “general notion of a reduction […] inherent to the notion of self-reducibility”? [migrated]

While reading "Computational Complexity: A Conceptual Perspective" by Oded Goldreich, I have come across the following passage, which I simply cannot get my head around: Note that the general ...
3
votes
1answer
52 views

Efficient algorithm to determine if a lambda calculus term is equivalent to one without a given free variable

Consider the following problem: given a lambda calculus term $t$ and free variable $v$ determine whether $\phi(t,v)$, where $\phi(t,v) := \exists t'. t' \equiv t \land v \notin FV(t')$. This problem ...
1
vote
1answer
15 views

Evaluation of $\beta$-Reduction with Parentheses in $\lambda$-Calculus

I'm studying $\lambda$-calculus, and had a question regarding an exercise I came across. I understand that $\lambda$-calculus uses three main strategies of evaluation, but I'm having trouble applying ...
2
votes
1answer
20 views

Resource Reservation: No Greedy Approach?

I'm considering the general resource reservation problem: n processes, m resources. Each process requests a set of resources and each resource can be used by exactly one process. Processes are only ...
1
vote
1answer
17 views

Reducing 3SAT to MAX-3SAT

I have the following problem: Consider the MAX-3-SAT problem: given a Boolean function in Conjunctive Normal Form (CNF) determine the maximum number of clauses that can be satisfied. Prove that ...
1
vote
1answer
120 views

How to reduce 3-COLOR to 42-COLOR?

The requirement is that two adjacent vertices have different colors, and max. 42 colors. I show that $ \text{42-COLOR} $ is in NP and then I must reduce it from $ \text{3-COLOR} $. Here it becomes ...
0
votes
1answer
28 views

Karp reduction from NP-hard problem to unknown problem

If I know that problem $A$ is NP-hard, but know nothing of problem $B$ and I know that the following Karp reduction is true: $$A \to B \, .$$ Is it correct to conclude that $B$ must also be NP-hard?
1
vote
1answer
34 views

Reduce ATM to REGULAR_TM

Consider $\mathsf{REGULAR_{TM}} = \{\langle M \rangle \mid \text{$M$ is a TM and $L(M)$ is a regular language}\}$. Let $S$ be the following algorithm, which solves $\mathsf{A_{TM}}$: “On input $\...
1
vote
2answers
108 views

Is it decidable that a context free language contains a given regular language?

I've been asked to solve this problem, but I'm completely stuck now. Is the set $\{G \in\text{CFG} \mid L(G)\supseteq L(A) \}$ where A is DFA fixed beforehand decidable? I know I've to find a ...
2
votes
1answer
26 views

Why do we have to make variables unique when evaluating $\lambda$-calculus?

I'm studying $\lambda$-calculus and came across a problem that I'm not sure how to understand. More specifically, it's about evaluating $\lambda$-calculus expressions using $\beta$-reduction. I was ...
0
votes
0answers
14 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
19 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
14 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
24 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
46 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
20 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
40 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 ...
2
votes
1answer
43 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. ...
1
vote
1answer
31 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
119 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
38 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
82 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
30 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 \;:\; (\...
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
27 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 ...
-1
votes
0answers
20 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 ...
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
108 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 ...
1
vote
2answers
83 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
45 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
40 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 ...
0
votes
2answers
91 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. If anyone could ...
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 ...
-1
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
2answers
37 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
31 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 ...