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

Question about reduction Proof

I've recently seen a proof that the set of Turing machines $L = \{encode(M) |L(M) \text{is closed under reversal}\}$ is not decidable. The proof used following idea: Reduce from the $A_{TM}$ problem ...
2
votes
0answers
26 views

How far would complexity hierarchies collapse if $L\in CoNP$ is $L\in NPH$?

Let $L\in CoNP$. Assuming that $L\in NPH$, what would we get? So, as $L\in NPH$ then every language $A\in NP$ has a reduction $A \leq L$. This would mean that $\overline{L} \leq L$ as well. By ...
0
votes
1answer
55 views

Prove that the Language $L=\{code(M)\;|\;L(M)\; \text{is closed under reversal}\}$ is undecideable

I want to solve this problem using Many-One-Reduction, which involves, if I understood it correctly, reducing another problem on the problem stated in the title, i.e. $$ H \leq_M L $$ I would try ...
0
votes
1answer
27 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 ...
3
votes
1answer
190 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 ...
0
votes
1answer
57 views

Is $L=\{\langle M\rangle\mid L(M)\subseteq HP\}\in coRE$?

My intuition is that $L\notin coRE$, but I haven't managed to prove that $HP \le L$, as previously I only saw reductions from $HP$ or from $\overline{HP}$ with $f$ such that $f((\langle M\rangle,x))=\...
6
votes
3answers
1k views

Mapping reductions for dummies

I am having trouble understanding a mapping reduction and I would appreciate your help. Define $\quad \begin{align} A_{TM} &= \{ \langle M, w \rangle \mid M \text{ Turing machine}, w \in \...
0
votes
1answer
27 views

Proving undecidability of a language with mapping reductions

I'm referring to questions like this one: Mapping reduction to show NeverHalt is undecidable I understand with Turing reductions, you have to use oracle calls of the unknown language you're trying to ...
1
vote
0answers
25 views

Is the problem “find the sequence of $N$ numbers between 1 and $D$ with least cost”, NP-hard?

Consider sequences $p=(p_1,\dots,p_N)$ (the order matters) of length $N$, where $p_i\in\{1,\dots,D\}$ for fixed $D$. Moreover, consider a cost function $c:\{1,\dots,D\}^N\to\mathbb{R}$ which comply $c(...
4
votes
2answers
8k views

Reduction from set cover problem to vertex cover problem

Although the reduction from vertex cover problem to set cover problem is quite simple, I did not find anywhere the reduction in the opposite direction. From the similarity in the type of problems, I ...
0
votes
1answer
25 views

Is this variation of the traveling salesman problem NP-hard

Consider the following setting. You have $n$ cities, and there is a cost to travel from a city $i$ to a city $j$ given by $c_{ij}>0$ where $c_{ij}\neq c_{ji}$. Moreover, if you are traveling to ...
0
votes
0answers
38 views

Is this combinatorial seach problem NP-complete?

The context: Consider the following optimization problem. Let $f_1,\dots,f_L:\mathbb{R}\to\mathbb{R}$ arbitrary (continous) functions for $L>1$ and $x_k\in\mathbb{R}$ evolve according to $$ x_{k+1}...
-1
votes
1answer
40 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} ...
0
votes
1answer
17 views

If $L_1\in R$ and $L_2$ is non-trivial language then $L_1\leq L_2$

Language $L$ is trivial if $L=\varnothing$ or $L=\Sigma^*$. I'm trying to prove the following theorem: If $L_1\in R$ and $L_2$ is non-trivial language then $L_1\leq L_2$. If $L_2$ is non-trivial the ...
0
votes
1answer
19 views

How to prove that $L_{D}\leq L_{U}$?

I have the following two languages: $$ L_{U}\triangleq\left\{ \langle M,x\rangle\,:\,M\text{ accepts }x\right\} ,L_{D}\triangleq\left\{ \langle M\rangle\,:\,M\text{ accepts }\langle M\rangle\right\} $...
5
votes
1answer
170 views

Weakest reduction for P-completeness

It is common to define $P$-completeness with respect to logspace many-one reductions. I am looking for a complexity class $C$ such that if $C=P$ then all problems in $P$ are $P$-complete under many-...
7
votes
1answer
3k views

Does two languages being in P imply reduction to each other?

Given two languages $L_1$ and $L_2$ that are in $\mathsf{P}$, can it be proven that there is a polynomial time reduction from $L_1$ to $L_2$ and vice versa? If so, how? I noticed that if $L_1$ is the ...
0
votes
1answer
43 views

Reduction of the diagonalization language to the universal language

I'm going through Jeffrey D. Ullman's Introduction to Automata Theory, Languages, and Computations. The author reduces an instance of the membership problem in $L_d$ (diagonalization language) to a ...
1
vote
1answer
18 views

Is there a mapping reduction for every two language $A$ and $B$ to some language $C$?

One of my friend told me that there is a language $C$ for every two languages $A$ and $B$ s.t $A \leq_{m} C$ and $B \leq_{m} C$ , he simply define two languages $A’=\{0w|w \in A\}$ and $B’=\{1w|w \in ...
1
vote
1answer
23 views

How to prove that the reduction relation is not symmetric

I know that the reduction relation is not symmetric. Writing formal proofs is the main core of the course I take on Theory of Computation. So I'm trying to prove that theorem. For that I need to show ...
2
votes
1answer
37 views

How is Hypergraph Isomorphism (HI) reduced to Graph Isomorphism (GI) in polynomial time?

This question states that the problem of Hyper-graph Isomorphism is equivalent to Graph isomorphism. I have not been able to find a description of the reduction so I am wondering how that might work ...
1
vote
1answer
33 views

How to prove NP-hardness of a Hamiltonian Path problem by reducing longest-path problem?

I know how to prove longest-path problem by reducing Hamiltonian Path problem. Here I want to prove NP-hardness of a Hamiltonion Path problem by reducing longest-path problem. (pretend we know longest-...
0
votes
1answer
37 views

Reduction from Clique to IS degree at most 4

This is from the Algorithms textbook by Dasgupta,C. H.Papadimitriou,andU. V. Vazirani question 8.6 (b) that asks: Edit: And missing from the pic as @Nathaniel points out in his answer below: "...
-2
votes
1answer
44 views

Reduction from 3SAT to SUBSET-SUM

The reduction from 3SAT to SUBSET-SUM includes building a table as follows: Where base 10 representation is used for the rows in the table. I would like to know if the reduction will still be correct ...
0
votes
1answer
966 views

Condensed Nearest Neighbor Explanation

I have a question regarding the Condensed Nearest Neighbor algorithm from ...
1
vote
2answers
134 views

Change the structure from 3SAT to 1in3 3SAT

There is a variable set V = {x1,x2,x3} and clause set C1={x1,x2,-x3} C2={x1,-x1,-x2} C3={-x1,-x2,x3} C4={x2,x3,-x3}. For this structure, no matter each variable is positive or negative, the clause can ...
0
votes
1answer
21 views

Show that a set is turing reducible to another set

Consider an operator $+$ defined on $P(N)$ as follows: $A + B = \{2x\mid x \in A\}\cup \{2x + 1\mid x \in B\}$ Show that both $A$ and $B$ are Turing-reducible to $A+B$ I am kind of confused about this ...
1
vote
2answers
49 views

Proving a problem is NP Hard

Consider the following problem: Given a weighted directed graph $G$, determine if $G$ has a cycle whose total weight is $k$. All edge weights are integer but might be negative. $k$ is not an inputted ...
1
vote
1answer
29 views

Proving Undecidability with reductions - Why do some proofs not use an Oracle?

I'm specifically referring to this group of questions here: https://www.cs.rice.edu/~nakhleh/COMP481/final_review_sp06_sol.pdf So as I've learnt it, say we want to prove a new Language L is ...
0
votes
1answer
32 views

Which of these properties hold for all FO theories? (but not regarding fragments thereof)

Which of these properties hold for all FO theories? (but not regarding fragments thereof) a. Decidable b. At least expressive as propositional logic c. NP-complete a) Decidable: no, some first order ...
2
votes
1answer
76 views

How can I prove the following problem is NP complete?

The problem: I have a list $\displaystyle S=\{s_{1} ,s_{2} ,\dotsc ,s_{n}\}$ places. Each unordered pair of places has cost and gain: $\displaystyle c\{s_{i} ,s_{j}\} \in \mathbb{N}$, $\displaystyle g\...
1
vote
1answer
41 views

Covering maximal number of sets using fixed number of elements

I've encountered some problem which seems general enough to have already been solved. There is a set of objects $O=\{o_1, o_2,\dots,o_k\}$ and a family of sets $A_1,A_2,\dots,A_t \subseteq O$. For ...
2
votes
1answer
291 views

Invertability of Karp reductions

Karp reducibility between NP-complete problems $A$ and $B$ is defined as a polynomial-time computable function $f$ such that $a \in A$ if and only if $f(a) \in B$. I am interested in polynomial-time ...
0
votes
2answers
32 views

Unrecognizability of $L(M_1) \cap L(M_2) = \emptyset$

Let's define a language $$C = \{ \{M_1, M_2\} \mid M_1, M_2 \text{ are TMs s.t. } L(M_1) \cap L(M_2) = \emptyset \}$$ We have to show that $C$ is unrecognizable. I am having trouble going on about ...
0
votes
1answer
74 views

On FPTAS and many one parsimonious reductions

We have two $NP$ complete problems $\Pi_1$ and $\Pi_2$. Suppose $\Pi_1\rightarrow\Pi_2$ be a many one parsimonious reduction. If $\Pi_1$ has an FPTAS then does $\Pi_2$ also have? If $\Pi_2$ has an ...
1
vote
1answer
55 views

3Col reduction Variation, Special edges

I have a question concerning NP reduction. My question asks me to show that if I have a graph with Edges that connect 3 nodes together instead of 2, (Y style I assume). I need to prove that finding ...
1
vote
0answers
71 views

Proving B-Min-Cost Strongly connected Subgraph is NP-Complete

We have a strongly connected directed graph where each edge has positive integer weights. We are also given a $B \in \mathbb{N}$. Does there exist a strongly connected subgraph where sum of edge ...
1
vote
1answer
2k views

Half-SAT intractability proof

I've been struggling lately with a problem that was in my last complex algorithms exam, and I can't find a solution. The problem is as follows: Half-SAT is a problem where C is a CNF boolean formula ...
2
votes
1answer
73 views

How is this reduction of 3-SAT to Half-SAT not valid? [duplicate]

I am studying algorithms and there is a question in CLRS called the Half-SAT problem We are given a 3-CNF formula with n variables and m clauses where m is even. We wish to determine whether there ...
1
vote
0answers
31 views

Polynomial variable of inapproximability after reduction

I proved the inapproximability of a problem that, given a multigraph $G = (V, E)$ and a set of vertices $U \subseteq V$ tries to maximize a score $f(U)$ whose value depends on the edges of the graph, ...
7
votes
2answers
4k views

When problem A reduces to problem B, which problem is more complex?

When discussing complexity classes, when we say that problem $A$ reduces to problem $B$, are we saying that problem $A$ is at least as complex as problem $B$, or the other way around?
2
votes
1answer
80 views

How does strong NP-completeness agree with encoding complexity?

I've recently read about the concepts of weak and strong NP-completeness, but faced a problem in wrapping my head around them. I've understood that problems which have numerical parameters (like ...
0
votes
1answer
200 views

Undecidability of closure under reverse of language accepted by TM

Prove that the following problem is undecidable using a reduction: Given a Turing machine $S$, does $S$ accept a word $w$ iff it accepts its reverse $w^R$? There is a solution here, which I don't ...
2
votes
2answers
267 views

Circuit satisfiability problem : SAT-C to SAT-2C

I have the following language : $L=\{\langle C_1,C_2\rangle \text{ | } C_1 \text{ and } C_2 \text{ are two circuits that calculate different function}\}$. We can call this language SAT-2C. Prove that ...
2
votes
1answer
16 views

Padding a 2SAT clause

In http://web.mit.edu/neboat/www/6.046-fa09/rec8.pdf, I see that they pad a 2SAT clause $(x\vee y)$ to make it a 3SAT clause by writing $(x\vee y\vee p) \wedge (x\vee y\vee \neg p)$. Why doesn't $(x\...
1
vote
2answers
31 views

Reduction from Independent Set with fixed vertex to Independent Set

I was looking to solve this reduction, but I dont see how to construct the new graph. It seems very simple but I'm not capable of do it. I give you the complete explanation about this reduction. We ...
5
votes
2answers
6k views

Proving that the shortest simple path problem between two vertices $s$ and $t$ in a graph is NP-complete

How to show that the shortest simple path problem between two vertices $s$ and $t$ (finding a minimum weight path between $s$ and $t$) in a graph is NP-complete? I saw the following proof in a ...
0
votes
1answer
135 views

Mapping reduction from $A_{TM}$ to $INFINITE_{TM}$ same as to $ALL_{TM}$?

I was trying to solve a problem with a mapping reduction from $A_{TM}$ to $INFINITE_{TM}$, and came across a solution that was 100% identical to another solution I saw for $A_{TM} \leq_M ALL_{TM}$. ...
0
votes
0answers
34 views

Show that a set is reducible to another set

Consider an operator $+$ defined on $P(\mathbb{N})$ as follows $$A + B = \{2x:\ x\in A\}\cup\{2x + 1:\ x\in B\}$$ Show that $A$ is $m$-reducible to $A+B$ and $B$ is $m$-reducible to $A+B$ As per the ...
1
vote
2answers
46 views

If $f$ reduces $L_1$ to $L$ and also $L_2$ to $L$ is $L_1=L_2$

If the same $f$ reduces $L_1$ to $L$ and also $L_2$ to $L$ does it imply that $L_1=L_2$? My intuition says no, but I couldn't find a counterexample.

1
2 3 4 5
22