Skip to main content

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
-1 votes
1 answer
51 views

if there is a 3/2 approximation algorithm for independent set then there is a 3/2 approximation algorithm for vertex cover?

if by absurdly there is a 3/2-approximation algorithm for INDIPENDENT SET then does there exist a 3/2-approximation algorithm for VERTEX COVER? the implication should be true because independent is ...
PatrickBateman's user avatar
0 votes
1 answer
53 views

Reduction from a language with unknown decidability to HALT

We were taught to use reductions in order to show that a given L is undecidable. My question is, given some definition of a new L, is there a way to find a reduction $$ L\leq_mHALT $$ So that I can ...
John's user avatar
  • 1
0 votes
1 answer
60 views

L = {⟨M⟩ : there does not exist w ∈$Σ^*$ such that M rejects w } is in coRE?

given this lanauge: $L=\left\{\langle M\rangle\right.$ : there does not exist $\mathrm{w} \in \Sigma^*$ such that M rejects $\left.\mathrm{w}\right\}$. how can I determine whether it is in $R, R E \...
user1701057's user avatar
2 votes
2 answers
616 views

Is it NP-hard to decide the existence of n subsets picked from n lists of subsets the union of which contains at most s elements?

You are given $n$ lists. The $i$-th list contains $k_i$ subsets of $\{1, \ldots, m\}$. You are also given an integer $s$. You should decide whether it's possible to pick up exactly one element (that ...
Vladislav Bezhentsev's user avatar
-1 votes
1 answer
110 views

Understanding reductions and notation

I am currently working through Sipser's Introduction to the Theory of Computation. In chapter 5, he defines that a Language $A$ is mapping reducible to language $B$, written $A\leq_m B$ if there is a ...
talon23's user avatar
0 votes
1 answer
172 views

System of equalities and inequalities is NP-hard using a reduction from 3COLORING

We are require to show that a problem where the input is a system of equalities and inequalities, each involving polynomials of degree at most 2 (with integer coefficients) in n real variables x1, x2,...
staz6's user avatar
  • 25
4 votes
1 answer
91 views

Is there such a thing as $coW[1]$-hardness?

I have a problem $\mathsf{A}$ and I would like to analyze its (parameterized) computational complexity. I found a parameterized reduction from the complement of the independent set ($\mathsf{coIS}$) ...
nuss_ecke's user avatar
1 vote
1 answer
36 views

Concrete example of a set with a lower degree of unsolvability

Post's problem, posed in 1944 by Post, was to know if there is a recursively enumerable set, which, being undecidable, was not equivalent to the Halting problem under Turing reducibility. While I've ...
user6767509's user avatar
2 votes
2 answers
368 views

How complement of ETM is semidecidable

If ETM = {<M> ∣ M is a Turing Machine and L(M) = ∅}, how can I prove that the complement of ETM is semi-decidable?
Essie's user avatar
  • 21
0 votes
2 answers
71 views

How can a $P(n)$ run in polynomial time if it calls $R(m)$ which has exponential time

We have a procedure $P(n)$ that makes multiple calls to a procedure $Q(m)$, and runs in polynomial time in n. Unfortunately, a significant flaw was discovered in $Q(m)$, and it had to be replaced by $...
Pratik Hadawale's user avatar
4 votes
2 answers
112 views

Do all NP-hard problems have a reduction from one to another (Either A $\leq_m$ B or B $\leq_m$ A)

Given two problems, $A$ and $B$, that are NP-hard. Is either one of the following is true? $A \leq_m$ B $B \leq_m$ A In other words, is there always a relationship between any two arbitrary NP-hard ...
Andrew Baker's user avatar
0 votes
3 answers
187 views

Sorting Numbers in O(N)?

Why is sorting numbers Omega(nlogn)? I'm thinking of an reduction algorithm where: For all the numbers x_i, we create a point (x_i, 0) on a 2d graph. Fit a line directly to the right starting from ...
Mike Rain's user avatar
2 votes
1 answer
64 views

Is finding a Polytime reduction from $L_1$ to $L_2$ equivalent to proving $L_2 \in P \Rightarrow L_1 \in P$

I often hear NP-completeness as problems such that, if they were in $P$ all problems in $NP$ are in $P$. The true definition, though, is that NP-complete is a set of languages in NP that all languages ...
Ank i zle's user avatar
  • 153
0 votes
1 answer
43 views

Do reductions (in NP and other classes) follow a linear path?

NP has several complete problems, which reduce to one another. In this sense, they are all "equal" in terms of hardness. There are other problems in NP that are also "equal" to one ...
Loic Stoic's user avatar
0 votes
0 answers
34 views

Reduction between problems where problem A solves problem B with probability $\frac{2}{3}$

Suppose we have a problem, $A$, and a machine $T_A$ that solves $A$. Now, let's say we have a problem $B$ that is solvable with a polynomial number of calls to $T_A$, and we call $T_B$ the machine ...
Loic Stoic's user avatar
0 votes
1 answer
102 views

Possible reduction from SUBSET-SUM

Given is a multiset $S$, a finite set $T = \{t_1, t_2, t_3\}$, and an integer $k \in \mathbb{N}$. Let $v(t_j)$ be a set of values $\in \mathbb{R^+}$ of length $|T|$ that can be assigned to $s_i$, and $...
joachimkristensen's user avatar
0 votes
0 answers
33 views

Reduction between a decidable language $L$ and $\Sigma^*$

Is there a reduction between a decidable language $L$ and $\Sigma^*$?
fva's user avatar
  • 1
1 vote
1 answer
129 views

Correct defintion polynomial-time reduction

I have frequently seen two different definitions of polynomial-time reduction. In the following let $A, B \subseteq \Sigma^*$ be decidable problems. I will try to formulate the definitions in my own ...
Polgerta's user avatar
0 votes
1 answer
50 views

If $B \in RE$ then $A \in RE$ - Reduction

I know that if there is a Turing Reduction from $A$ to $B$, say $A \le_T B$, and $B \in R$ then $A \in R$. I also know that Turing Reduction is for Decision, and not Recognition. Is it possible to ...
Geo's user avatar
  • 47
0 votes
1 answer
45 views

Prove by reduction that language of TMs accepting only words starting with 101 is undecidable

Before an exam in Computability I go through questions from last year's test. So the question is: $$A= \{ \langle M\rangle x | M \text{ is a TM and accepts } x \}$$ $$ L = \{ \langle M \rangle | M \...
Konstantin's user avatar
2 votes
0 answers
29 views

Are $\mathsf{L,NL}$ closed under reverse operation?

for a language $L$ we define $rev\left(L\right)=\left\{ \sigma_{n}\cdot\ldots\cdot\sigma_{1}\mid w=\sigma_{1}\cdot\ldots\cdot\sigma_{n}\in L\right\} $. My question is, are $\mathsf{L,NL}$ closed under ...
Ariel Yael's user avatar
3 votes
0 answers
49 views

Reduction from $\mathsf{ALL}_{\mathsf{TM}}$ to it's complement

I'd like to know if there's a reduction $\mathsf{ALL}_{\mathsf{TM}}\leq_{m}\overline{\mathsf{ALL}_{\mathsf{TM}}}$ where of course $\mathsf{ALL}_{\mathsf{TM}}=\left\{ \left\langle M\right\rangle \mid\...
Ariel Yael's user avatar
2 votes
0 answers
57 views

Proving the language 2-SIMPLE-PATH is in NL

The Question I define the language$$\mathsf{2-SIMPLE-PATH}=\left\{ \left\langle G,s,t\right\rangle \left|\begin{array}{c} \mathsf{there\;are\;two\;different}\\ \mathsf{simple\;paths\;from}\;s\;\...
snatchysquid's user avatar
0 votes
0 answers
66 views

Reduction from Diophantine Equation Problem to Halting Problem

I want to study the reduction from the Diophantine Equation Problem (Hilbert's tenth problem) to the Halting problem. Can you either explain it to me or give me a credible source from which I can ...
Mgh's user avatar
  • 1
0 votes
1 answer
208 views

Is this sorting problem NP-complete?

Consider array $A=(a_1,a_2,...,a_n)$ such that $a_i$s are positive integers. Moreover, we have $k$ binary tuples, each with length $n$. In each iteration, we choose one of those tuples, and decrease ...
Soroush Vahidi's user avatar
1 vote
1 answer
21 views

Are the indices of variables in the formula variable?

Let $L$ be an arbitrary language in $\Sigma_3$. Thus it can be written that $x \in L \Leftrightarrow \exists y^{p(|x|)} \forall z^{p(|x|)} \exists w^{p(|x|)} \langle x,y,z,w \rangle \in B$ where $p(\...
advocateofnone's user avatar
1 vote
1 answer
33 views

Reduction from $2$-Partitioning to (simple) pairwise $2$-Partitioning

I'm currently stuck showing $NP$-hardness of a problem of mine. An instance of my problem (I call it (simple) pairwise $2$-Partitioning) is given by the following: Given a set of tupels $B=\{(b_1,1),\...
Felix's user avatar
  • 161
-1 votes
1 answer
35 views

A sufficient condition for unsatisfiability

Let $\varphi = \bigwedge C_k$, in which $C_k$ is a clause in X3SAT (exactly-one 3SAT or one-in-three 3SAT). That is, $C_k = (l_i \odot l_j \odot l_u)$ such that $l_i \in \{x_i, \overline{x}_i\}$ for ...
Latif Salum's user avatar
0 votes
2 answers
161 views

Ιf 3SAT reduces to its complement then NP=coNP

Can you please explain to me why the following is true? Ιf 3SAT reduces to its complement then NP=coNP. Thoughts: 3SAT is NP-complete so for every X in NP $X \leq 3SAT$ $\overline {3SAT} $ is NP-...
Hjm's user avatar
  • 47
0 votes
1 answer
57 views

$L_1= (1$ { $0, 1$ }$^∗) \cup ${ $0x | x \in L$} is NP- complete

If L is NP-complete then how can I prove that $L_1$: $L_1= (1$ { $0, 1$ }$^∗) \cup ${ $0x | x \in L$} is also NP- complete. My thoughts: A reduction from (for example) SAT to L can be converted to a ...
Hjm's user avatar
  • 47
0 votes
1 answer
410 views

4DM is NP-complete

Is 4DM NP-complete? An instance of 4DM consists of four disjoint sets X, Y, W and Z of size k, and a set Q of quadruples $Q = \{ (x, y, w, z) \mid x ∈ X, y ∈ Y, w ∈ W, z ∈ Z \}$ Question: Is there a ...
Hjm's user avatar
  • 47
1 vote
1 answer
408 views

Variation of 3-SAT

I already know that SAT and 3-SAT are NP-complete. If in 3-SAT the Boolean expression should be divided to clauses,such that every clause contains at most (in the original problem it says exactly) ...
Hjm's user avatar
  • 47
0 votes
2 answers
148 views

Is a language semi-decidable iff it is reducible to ATM?

Thank you. I see how it makes sense going in the opposite direction but i need help proving that this is true. Below is the definition of ATM. ATM={<M,w>| a TM, M accepts w} The question from my ...
Carrey's user avatar
  • 1
-1 votes
1 answer
65 views

Showing NP-completeness of a graph problem with vertex capacities

The problem: Given an undirected graph G = {V, E}, a source-vertex s, and each vertex having a "capacity" between 0 and |V|, is there a tree which covers all vertices and does not extend ...
kanpaitech's user avatar
-2 votes
1 answer
32 views

How to prove that it is NP-complete?

I was trying to do this exercise, but I don't know how to solve this problem is NP-complete, what reduction to do. There is a network N of n people, in which every person i is associated with a subset ...
Alfonso Beniamino's user avatar
1 vote
1 answer
142 views

How to reduce universal language to language of all turing machines that deduce all palindromes?

Let $S$ be language $$\{\langle M\rangle \mid(\forall x \in \Sigma^*)[x \in L(M) \iff x^R \in L(M)]\}.$$ How can I show that $L_U \le_m S$ and $L_U \le_m \bar S$ where $L_U$ is universal language and $...
Rikib1999's user avatar
  • 125
1 vote
1 answer
71 views

$L=\{<M>|M~is~a~TM~and~L(M)=\{0^n1^n|n\ge0\}\}$

About the language $L=\{<M>|M~is~a~TM~and~L(M)=\{0^n1^n|n\ge0\}\}$ I want to determine if it is in RE / coRE or neither. I think that I found a mapping reduction from $\overline{A_{TM}}$ to $L$, ...
Geo's user avatar
  • 47
1 vote
1 answer
34 views

Reducing problems to solve easier problems

Is there any instance where a problem $A$ can be reduced to a problem $B$ where $B$ is easier to solve than $A$? I've been learning about NP-Hardness recently and seems that the answer is no. Whenever ...
Ludwig's user avatar
  • 113
0 votes
0 answers
20 views

To Prove NP-Completeness [duplicate]

Given a Directed Graph G, and some subsets of vertices T1,T2,..Tn(These subset can intersect) , is there a path in this graph such that it is acyclic and contains exactly 3 vertices from each Ti. I'm ...
uzu's user avatar
  • 1
1 vote
1 answer
195 views

Show problem is NP-hard

I'm preparing for my exam and I got stuck on the following problem: The gardening problem: We have access to a set of different types of seeds and a number of plant pots.For each plant pot, there is ...
kim120's user avatar
  • 21
1 vote
1 answer
54 views

Mapping reduction - Bit Flip

Let $L=\{<M> | M$ is a TM, $L(M)\ne \emptyset$ and $\forall x\in L(M), \overline{x} \notin L(M) \}$ While $\overline{x}$ is the bit flip of $x$. I want to show a mapping reduction to prove that ...
Geo's user avatar
  • 47
0 votes
2 answers
375 views

Reduction from SUBSET SUM to COIN CHANGING

The COIN-CHANGING problem is NP-complete, but I am having difficulty finding a proof for its NP-hardness in the form of a reduction from another NP-complete problem ...
al5719's user avatar
  • 3
1 vote
1 answer
36 views

Choosing the ideal problem to prove the hardness

I am research scholar currently working in complexity theory. Recently, i have started working on hard proofs and reductions. It is very well established that there is a polynomial reduction from ...
Balchandar Reddy's user avatar
3 votes
1 answer
169 views

NP-hard $k$-SAT variant with exactly $\ell$ occurrences per variable

For the purpose of this post, let $k$-SAT be SAT with exactly $k$ literals per clause, as opposed to the more common meaning of at most $k$ literals per clause. With the purpose of proving some ...
J. Schmidt's user avatar
0 votes
1 answer
45 views

NP-hard (3-)SAT variant with $n$ clauses and $f(n)$ variables

With the purpose of proving my problem NP-hard, I'd like to reduce from a SAT variant (which of course should remain NP-hard) in which not two parameters are present (typically $n$ clauses and $m$ ...
J. Schmidt's user avatar
1 vote
1 answer
236 views

Graph Isomorphism Problem: decisional vs functional

The Graph Isomorphism Problem is a classic in Computer Science. In its decision version $(DGI)$, we are given two graphs $G$ and $H$ and we are asked if there exists an isomorphism between the two. In ...
VashTheStampede's user avatar
0 votes
1 answer
27 views

Assume we know that (1) $A$ reduces to $B$ in time $O(f(n))$ time and (2) $B$ reduces to $A$. What can we say about the time for $B$ -> $A$?

The question is basically the title. If two NP-Complete problems reduce to each other, do we know that the reductions take equal amounts of time? What about space? Does this apply for all 'invertible' ...
Andrew Draganov's user avatar
2 votes
1 answer
82 views

Show this 2D Grid Set Cover-ish problem is NP-Complete?

Given a $n \times m$ rectangular grid of cells each with an integral weight: $w_{i,j}$ and two integer parameters $w \ge 2$ and $h \ge 2$ (for group width and height respectively). Select the subset ...
Matt D's user avatar
  • 313
1 vote
1 answer
48 views

show for any Languages $L_1$ and $L_2$ exists a Language $L$ with $L_1 \leq_{log} L$ and $L_2 \leq_{log} L$

This is an old exam question, but I never found a solution or somebody who could explain it to me. Here is the problem statement: Let $\Sigma$ be an alphabet with |$\Sigma$| $\geq 2$. Show that for ...
456c526f's user avatar
3 votes
0 answers
40 views

Can fine-grained hardness be proved directly from classical hardness (e.g., $\sf P \neq NP$) in some way?

I have just learnt about some typical result of fine-grained hardness in 15-455 by Prof Ryan: CNF-SETH implies ${\sf DIAMETER} \notin {\sf TIME}(mn^{1-\epsilon})$. (Here DIAMETER stands for the graph ...
Heda Chen's user avatar
  • 311

1
2
3 4 5
26