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
3
votes
0answers
30 views

Reduction from Edge-Coloring and Vertex-Coloring to a new problem

I have a question from a test I did and failed, a question I failed to do. In short: the question is about reduction from Vertex-coloring and Edge-coloring, to a new problem they have defined. The new ...
0
votes
1answer
59 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 ...
1
vote
2answers
46 views

Reduction between CLIQUE to SUBSET SUM

I have a question from a test that I failed to pass, I failed to do the question. The question is about the reduction between Clique and Subset Sum. I tried to find an explanation for this on the ...
0
votes
0answers
28 views

Reduction from IS problem to other problem [closed]

Given graph 𝐺 = (𝑉, 𝐸) it is said that it is a star if there is a vertex $𝑣_0 ∈ 𝑉$ so that all the other vertices are connected exclusively to it (and not to ...
2
votes
1answer
36 views

Reduction from language in P to another language in NP

I have a question I was unable to do, from a last test I had. This is the question: Will be $A \in NP$ Let $c \in P$ be a language so that there exists $C \leq _pA$. Determine which of the following ...
5
votes
1answer
79 views

Reduction from the SAT problem to the NAE-SAT problem

I study complexity and computation independently. I have a problem that I can not solve. That's the problem: For the SAT problem, there is a version in which we receive as input phrase $\varphi$ in ...
1
vote
2answers
117 views

edge-coloring and vertex-coloring reduction problem

I study complexity and computation independently. I have a problem that I can not solve. That's the problem: Edge-Coloring problem, we get as input graph G = (V, E) and natural number k and ask "...
0
votes
1answer
16 views

Reduction from the Clique problem to the Odd Clique problem

I have a question that is not clear to me, and I have not been able to answer it from a test I had. This is the question: Let's look at the problem $Oclique$ , In it we get a graph $G = (V,E)$ , And ...
0
votes
1answer
31 views

Complications of a language that reaches a state of reject

I have a question that is not clear to me, and I have not been able to answer it from a test I had. This is the question Let's look at the language $L_\mathrm{reject} = ${ $\left \langle M,w \right \...
3
votes
1answer
37 views

edge-coloring reduction problem

I study complexity and computation independently. I have a problem that I can not solve. That's the problem: Edge-Coloring problem, we get as input graph G = (V, E) and natural number k and ask "...
1
vote
0answers
19 views

NP-Hardness of $\{ (S,k) | \exists S' \subset S \text{ s.t } \forall x \neq y \in S' \gcd(x,y)=1 \text{ and } \sum_{s \in S'} s \geq k \}$

I have been practicing NP-Hardness reductions and have been particularly interested in the language $L = \{ (S,k) | \exists S' \subset S \text{ s.t } \forall x \neq y \in S' \gcd(x,y)=1 \text{ and } \...
-1
votes
1answer
32 views

Reducing subsetsum to {<G, l, u> | G is a weighted graph that has a spanning tree with weight between l and u}

How can I reduce Subsetsum (or maybe other np-complete problem) problem to the problem below? input : a weighted graph $G$ and numbers $l$ and $u$. output : Does $G$ has spanning tree, $S$, such that $...
2
votes
1answer
33 views

Language in NPC and CoNP

A few days ago I had a test that I failed to pass, and it had a question that I failed to do. the question: given: $A \in NPC$ $A \in CoNP$ Determine which of the following statements is correct: $P\...
4
votes
2answers
107 views

tautology vs satisfiability

I had a test that I failed to pass, and it had a question that I failed to do. This is the question: Let us look at the language TAUTOLOGY: Collect all the phrases $\varphi$ so that each placement on ...
2
votes
1answer
65 views

Reduction from TSP to even TSP

I have a question from a test that I failed to pass, I failed to do the question. The question: Let's look at the problem of the even-length traveling agent. Given graph $G = (V,E)$ and a weight ...
2
votes
1answer
61 views

Complexity of the language that enters an infinite loop

A few days ago I had a test that I failed to pass, and it had a question that I failed to do. This is the question Let's look at the language $L_\mathrm{loop} = ${ $\left \langle M,w \right \rangle$ | ...
1
vote
1answer
21 views

Relationship between NP and CoNP

I have a question from a test that I could not pass, I could not answer the question and I am looking for help with this question This is the question Will be $A\in NP$ Suppose that $A\notin CoNP$. ...
3
votes
2answers
50 views

Reduction with CoNP and CoNPC

I have a question I was unable to do, from a last test I had. This is the question: Suppose that there is a language $A \neq \emptyset ,\sum{_{}}^{*}$ such that $A \in CoNP - CoNPC$. Determine ...
2
votes
1answer
21 views

Reduction with NPH

I have a question in complexities that I could not do. There will be D, E, F, three languages belonging to NPH. Suppose that the reductions exist $D \leq _P E$ and $E \leq _P F$. Determine which of ...
1
vote
0answers
31 views

Equivalence of algorithms with less than vs equal to constrains

Problem A: Given an algorithm $\mathcal{A}$ for $(I,k)$,$k\in \mathbb{N}$, $A$ return true $\iff$ There exist a subset $S\subseteq I$ s.t $|S| \le k$ some property hold. Problem B: Given an algorithm $...
-1
votes
1answer
34 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 ...
0
votes
1answer
26 views

Deteremine if $L = \{\langle M\rangle : L(M) \text{ consits of all words of prime length}\}$ is in $R$ or in $RE\setminus R$ or not in $RE$

Deteremine if $L = \{\langle M\rangle : L(M) \text{ consits of all words of prime length}\}$ is in $R$ or in $RE\setminus R$ or not in $RE$ I am trying to prove that $L$ is not in $RE$ by reduction ...
1
vote
2answers
121 views

Reduction from vertex-coloring problem to edge-coloring problem

A few days ago I had a test and could not pass it. This is a question I did not understand in the test. We will look at the Edge-Coloring problem, in which, as is well known, we get as input graph G =...
0
votes
0answers
16 views

Understand what this phrase is in the Turing

I had a test a few days ago and failed it. There was a question that was not clear to me. This is the question: For the purpose of describing the drawing on the tape of a Turing machine at each step ...
0
votes
1answer
26 views

How to know if language is in comp or np?

I'm new to the site. I had a test a few days ago and failed it, I had a question I did not understand. This is the question: Let's look at the FALSE language: Collect all the verses P in the form of ...
1
vote
1answer
38 views

SUBSET SUM reduction to PARTITION

This is the PARTITION problem: Given a multiset S of positive integers, decide if it can be partitioned into two equal-sum subsets. This is the SUBSET SUM problem: Given a multiset S of integers ...
0
votes
0answers
79 views

Proving that a problem is not FPT using reduction

In the Inclusive Vertex Cover problem, For a given graph $G=(V,E)$, each vertex $u\in V(G)$ has weight $u_{w} \in \mathbb{N}$ and value $u_{v}\in \mathbb{N}$. The value and weight of a set cover $S$ ...
0
votes
0answers
40 views

Connection between planar graph and vertex cover

I have two similar problems in which I'm trying to find a connection to help me solve one of them. In the first one I'm given a graph G = (V,E) , integer k, and vertex cover U of size k. The objective ...
0
votes
1answer
12 views

Reduction from 2 finite languages when one doesn't include epsilon and the other does

Just did a test about the subject that had the following question: I know it seems trivial and my first reaction was "well of course its true" but the epslilon kinda threw me off. $L_2$={ab,$...
0
votes
0answers
64 views

Reduction rules to lower bound minimum degree of a graph

I'm trying to come up with a list of rules that return an equivalent instance to the following problem, while eliminating all vertices of degree 2 or less from the graph: Given a graph $G=(V,E)$, the ...
0
votes
1answer
46 views

Issues in the proof of $E_{TM}$ is Turing reducible to $A_{TM}$

First definition: $A_{TM}$ = $\{ <M,w> | $M is a TM and M on w accepts$ \}$ Second definition: $E_{TM} = \{ <M> |$ M is a TM and L(M) = $\phi \}$ Let $T^{A_{TM}}$ be an oracle Turing ...
0
votes
0answers
30 views

Show that $3SAT$ is a polynomial reduction on $MSAT$, i.e. $3SAT \leq_p MSAT$ [duplicate]

The exact definition of $3SAT$ and $MSAT$ are as follows: $3SAT :=$ each clause has exactly 3 literals $MSAT :=$ At least half of the literals of every clause are True My intuition was, as we know ...
1
vote
0answers
38 views

Delivery problem, unsure which exact problem it is

I'm looking for guidance on how to reduce the following problem to a known problem or a suggestion for solving it altogether. Optimal / heuristic solutions or any other suggestions are greatly ...
0
votes
1answer
32 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
29 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
73 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
37 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 ...
1
vote
0answers
26 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(...
0
votes
1answer
28 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
39 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
42 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
26 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\} $...
0
votes
1answer
18 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
53 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
19 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
27 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 ...
1
vote
1answer
42 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-...
-2
votes
1answer
46 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
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
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
2 3 4 5
23