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
1 answer
54 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 $...
0 votes
0 answers
19 views

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

Is there a reduction between a decidable language $L$ and $\Sigma^*$?
  • 1
1 vote
1 answer
31 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 ...
0 votes
0 answers
16 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 ...
  • 37
0 votes
1 answer
29 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 \...
0 votes
0 answers
18 views

Is $L(M_{A_{TM}⤭})$ NP-Hard?

Let $A_{TM}=\{<M,w>|M~is~a~TM~and~M~accepts~w\}$, clearly it is NP-Hard. Let $M_{A_{TM}}$ be the DTM that recognizes $A_{TM}$. Define $M_⤭$ to be the TM obtained from $M$ by swapping the accept ...
  • 37
2 votes
0 answers
25 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 ...
1 vote
0 answers
21 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\...
2 votes
0 answers
42 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\;\...
0 votes
0 answers
50 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 ...
  • 1
0 votes
1 answer
104 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 ...
1 vote
1 answer
18 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(\...
0 votes
0 answers
31 views

Equivalence for Turing Machines is not Recognizable - Reduction DOUBT

I have a big doubt on this video about $EQ_{TM}$, especially on minute 5:11. Why is he saying that to reduce $ A_{TM}\lt_{m}\overline{EQ_{TM}} $ we need to create a machine M that rejects every input? ...
1 vote
1 answer
27 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),\...
  • 161
-1 votes
1 answer
34 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 ...
0 votes
2 answers
55 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-...
  • 37
0 votes
1 answer
31 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 ...
  • 37
0 votes
0 answers
17 views

Beta reduction and sequence of effect

The famous Monad is well known for handling effect in a functionally pure manner (e.g. IO Monad). On the other hand, in some application, runtime performance is the utmost interest and the compile ...
0 votes
0 answers
82 views

Reduction from Partition problem to the same problem with the input replicated multiple times

In a variant of the Partition Problem given a multiset $S = \{a_1,\dots,a_n\}$ of positive integer with the total sum $\sum_{i=1}^n a_i = m\,T$, we want to find out if exists a partition $S_1,\dots,...
  • 1
0 votes
0 answers
24 views

How to prove by reduction this (acceptance?) problem

At school I was assigned this example: Prove by the reduction method that it is undecidable whether for a given Turing machine M with the alphabet {a, b, _} holds aabb ∈ L(M). I think it's acceptance ...
  • 3
0 votes
0 answers
91 views

Reduction from LONGEST PATH to HAMILTONIAN PATH

LONGEST PATH is the decision problem asking if a simple path of at least $K$ edges exists in a graph $G$. The reduction from ...
  • 3
0 votes
1 answer
60 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 ...
  • 37
1 vote
1 answer
50 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) ...
  • 37
0 votes
2 answers
47 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 ...
  • 1
-1 votes
1 answer
39 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 ...
0 votes
0 answers
37 views

Can the airline scheduling algorithm (network flow) be extended to handle seating capacities?

The airline scheduling problem determines the minimum number of airplanes required to service a set of passenger flights, where a plane can service routes A$\rightarrow$B and C$\rightarrow$D if there ...
-2 votes
1 answer
30 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 ...
1 vote
1 answer
55 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 $...
  • 125
0 votes
0 answers
40 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$, ...
  • 37
1 vote
1 answer
32 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 ...
  • 13
0 votes
0 answers
19 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 ...
  • 1
1 vote
1 answer
148 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 ...
  • 21
1 vote
1 answer
45 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 ...
  • 37
0 votes
2 answers
45 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 ...
  • 3
1 vote
1 answer
24 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 ...
2 votes
1 answer
52 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 ...
0 votes
1 answer
29 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$ ...
0 votes
0 answers
161 views

Halting problem reduction to single digit numbers

I'm thinking of the solution for severaly days, but I'm not sure about my solution is on the correct way. I need to prove that the next problem is undecidable: Input: An N program which requires an y ...
1 vote
1 answer
159 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 ...
0 votes
1 answer
26 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' ...
0 votes
0 answers
15 views

Finite complexity meta-algorithm to generate (non-asymptotically) polynomial time shortcuts to EXPTIME problem of arbitrary input size

I might be able to find a polynomial time reduction to an EXPTIME algorithm of finite size, but is it possible for a finite-description-length algorithm to exist that finds polytime shortcuts for any ...
0 votes
0 answers
111 views

Reduce the independent set problem to the set packing problem

I got this question in my compsci homework and tried the reduction from the solution with an example and it doesn't seem to want to work. Here's the proposed reduction: The independent set problem ...
2 votes
1 answer
52 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 ...
  • 313
0 votes
1 answer
39 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 ...
3 votes
0 answers
39 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 ...
  • 191
1 vote
0 answers
55 views

Do all NP-Complete problems run in $O(c^n)$ time, as opposed to $O(c^{n^k})$?

According to the Wiki article on NP-Completeness, NP-Complete problems can be solved in $O(c^{n^k})$ time (I'll call this EXP-POLY time). However, shouldn't the bound on all their run times be the ...
  • 502
0 votes
1 answer
28 views

Reductions but no algorithms

in "Introduction to Automata Theory, Languages and Computations" by Motwani, Ullman and Hopcroft, when they need to prove, for instance, Rice's theorem, they reduce the universal language, $...
  • 1
2 votes
0 answers
30 views

Reductions from 3-SAT that won't work directly from SAT

Our prof talked about why it's good to know that 3-SAT is NP-complete because it's easier to craft reductions from it than from plain SAT. However, all the examples we've seen (reduction to ...
  • 21
1 vote
2 answers
142 views

An intuitive explanation of "provably complex combinatorial games"

It is very surprising to me that some combinatorial games such as generalized chess are EXPTIME complete. I have no idea why having a solver for a combinatorial game allows you to solve arbitrary ...
  • 3,472
0 votes
0 answers
62 views

Polynomial Reduction from 3SAT

Given an undirected graph $G=(V,E)$ where $V$ is a set of vertices, and $E$ is a set of edges and given a set $D$ where $D \subseteq V $ and $ \forall v \in V \setminus D \: \mid \: \exists w \in D : ...
  • 1

1
2 3 4 5
25