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
1answer
23 views

Multivariate polynomials

Given a Diophantine equation $p(x_1,x_2,...,x_n)$, Can I find a reduction from $\text{dioph}(\mathbb{N}) \leq \text{dioph}(\mathbb{N}_e)$? $\mathbb{N}_e$ is the set of even numbers. So I have to ...
1
vote
0answers
14 views

What if SAT Turing-reduces to a problem? [duplicate]

To show that problem is NP-hard, we take a known NP-hard problem and reduce it to the problem whose NP-hardness we want to prove. The reduction we need is polynomial time reduction. But If I take ...
0
votes
0answers
11 views

Denset-k-subgraph to ILP reduction [closed]

I have exercise: Show reduction Denset-k-subgraph to ILP (Integer Linear Porgramming). (Denset-k-subgraph is problem where there is graph G = (V, E) and two natural numbers k and t. We are ...
0
votes
1answer
54 views

Showing party invitation problem is np-complete

Suppose you and your $k - 1$ housemates decide to throw a party. Each housemate $i$ gives you a list $P_i$ of people she would like to have invited to the party. Depending on how much you like ...
1
vote
1answer
23 views

Is there any problem that is R-complete and RE-complete

R-complete, i.e. it is an analogue to all recursive language can be reduced to that problem and also recursive? Or is there a really such definition? RE-complete is described on wikipedia. But what ...
1
vote
1answer
37 views

Show Resource Allocation Problem is NP-Complete

We are given $n$ tasks and $m$ resources. Each task $i$ requires a set $S_i$ of resources to be active, and each resource can be used by at most one task. The Resource Allocation problem asks: given $...
3
votes
1answer
54 views

Is maximum edge-weighted triangle-free graph NP-hard?

Given a graph $G$ with weights $w_e$ on the edges, choose a subset $S$ of the ''edges'' such that $S$ doesn't contain any 3-cycles, maximizing $\sum_{e\in S} w_e$. Is this problem NP-hard? I thought ...
1
vote
1answer
33 views

Finding a suitable NP-complete problem for reduction

We are given a set of names and a set of papers with names written on each side of the paper (not necessarily different ones and either side of the paper can be empty). Can we place the sheets on a ...
1
vote
1answer
83 views

Is this partitioning problem NP-complete?

I have a sequence of points $(x_1, \ldots, x_n)$ and a function $f$ that maps every consecutive subsequence (ie. of the form $(x_i, x_{i+1}, \ldots, x_j)$) to a real number. I want to split this ...
0
votes
1answer
29 views

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

Let $L$ be recursively enumerable and $U$ be non-recursively-enumerable. Is it possible to reduce $U$ to $L$ recursively, $U\leq_R L$? Personally, I do not think this is possible. If we can reduce $U$ ...
1
vote
1answer
43 views

Reduction between these two languages

I'm given $L_\cap=\{\langle M_1\rangle\#\langle M_2\rangle\mid L(M_1)\cap L(M_2)\neq\emptyset\}$ and $L_U=\{\langle M\rangle\#w|M \text{ accepts } w\}$. How can I reduce the former to the latter: $L_\...
1
vote
1answer
13 views

Poly-time reductions for proving EXPTIME-hardness are _not_ enough?

Wikipedia says that in order to prove EXPTIME-hardness of our problem, we need to prove that every EXPTIME problem can be poly-time reduced to our problem. Here is a "counter-example" that bugs me. ...
2
votes
1answer
41 views

What is wrong with this reduction from vertex cover to binary programming?

I am trying to polynomial-time reduce the decision version of vertex cover to the decision version of binary programming. Here are the problem statements. Vertex Cover Decision Problem Instance: A ...
1
vote
2answers
28 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 ...
2
votes
1answer
68 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
29 views

Expectation 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
55 views

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

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
32 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
20 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
176 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
32 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 ...
3
votes
1answer
424 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
23 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
46 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 ...
3
votes
1answer
57 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
19 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
21 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
19 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
121 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
37 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
114 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
29 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
17 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
21 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
16 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
26 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
47 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
41 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
40 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
83 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
17 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
28 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 ...
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 ...