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
160 views

Reductions among two problems related to walks of length $k$

Consider the following two problems: A. Given a directed graph and a parameter $k$, determine if it contains a path (not necessarily simple) of length $k$. B. Given a directed graph, two vertices $s,t$...
0
votes
2answers
163 views

Is $MIN_{TM}$ not in $\overline{RE\cup coRE}$

Given the language: $MIN_{TM}$= $\{ \langle M,k\rangle: there\ exists\ a\ TM\ D\ s.t.\ L(M)=L(D)\ and\ D\ has\ less\ than\ k\ states \}$ I need to prove if this language is in $R$ or $RE-R$ or $...
5
votes
4answers
3k views

EQtm is not mapping reducible to its complement

This is a problem from Sipser's book (marked with an asterisk). $EQ_{TM} = \{(\langle M \rangle, \langle N \rangle)$ where $M$ and $N$ are Turing machines and $L(M) = L(N)\}$ We know that neither $...
0
votes
1answer
58 views

If two languages are decidable, can one be mapping reducible to the other?

If I have two decidable languages $A$ and $B$, is $A \leq_m B$ true? How would I show this?
1
vote
1answer
92 views

What is the polynomial time reduction between these two Hamiltonian cycle problems?

Problem 1: Given an undirected graph, return the edges of a Hamiltonian cycle, or correctly decide that the graph has no such cycle. Problem 2: Given an undirected graph, decide whether or not the ...
2
votes
1answer
37 views

Why are $L$-reductions defined the way they are?

I was reading about $L$-reductions and there was one part in the definition that I thought was interesting. I wanted to know what motivated people who came up with it to have it included in the ...
3
votes
2answers
109 views

Playing video games to solve SAT instances

This paper shows that computer games, such as Super Mario, are NP-hard, by reduction from SAT. It may be possible to use this reduction to help solve hard instances of SAT: use the reduction to ...
0
votes
0answers
40 views

Finding the smallest-cost way to deliver goods

I want to deliver products from various sources to various destinations such that the overall cost is minimized. We need to deliver these products while obeying our contractual obligatione with each ...
1
vote
1answer
38 views

For given reduction f, can show "if f(x) in 4NAE then x in 3SAT", but not "if x is not in 3SAT then f(x) not in 4NAE"

Claim: $3SAT \le_p 4NAE $, where reduction $f$ is defined as such: given a 3CNF formula $\varphi$, add to each clause a new literal $z$ (where $z$ is same literal for each clause), and return new ...
2
votes
0answers
95 views

3-partition problem without the restriction to triplets [closed]

In the standard 3-partition problem, there are $3 m$ integers, their sum is $m T$, and they have to be partitioned into $m$ subsets of sum $T$ and size $3$. Consider the variant without the ...
2
votes
2answers
512 views

A reduction of $HALT_{TM}$ to $A_{TM}$

A widely used example of reductions, is a reduction of $A_{TM}$ to $HALT_{TM}$. How to show the opposite reduction, meaning of $HALT_{TM}$ to $A_{TM}$, if possible.
1
vote
0answers
13 views

Is there a fpt reduction of a NP-hard problem towards a fpt parameterisation $K'-D' \in FPT$?

Question While trying to search for a (example of a) NP-hard problem that fixed-parameter reduces to another NP-hard problem that is known to be fixed parameter tractable, such as k-Vertex Cover, my ...
1
vote
2answers
145 views

NP-completeness of a Generalized Version of Subset Sum

I am curious about the NP-completeness (or if not, an efficient algorithm) for the following generalization of the subset sum problem: In subset sum, we are given a number $t$ and a collection $S$ of ...
1
vote
1answer
114 views

Complexity of specific cases of MAX2SAT

I know that MAX2SAT is NP-complete in general but I'm wondering about if certain restricted cases are known to be in P. Certainly the languages $L_k:=\{ \phi \,|\, \phi\,\text{is an instance of 2SAT ...
0
votes
1answer
80 views

Can an NP-Complete problem be reduced to an NP problem?

All NP problems can be reduced to NP-Complete problems, can an NP-Complete problem be reduced to a NP problem (non complete)?
0
votes
0answers
35 views

$A \leq_p {\overline{A}} \Leftrightarrow {\overline{A}} \leq_p A$

I want to prove that $$A \leq_p {\overline{A}} \Leftrightarrow {\overline{A}} \leq_p A$$. Does anyone have a Idea how to solve this ?
4
votes
1answer
101 views

MIS complexity in cubic triangle-free graphs

The question Complexity of Independent Set on Triangle-Free Planar Cubic Graphs asks for the complexity of the independent set problem in triangle-free planar cubic graphs. In the statement of the ...
0
votes
1answer
631 views

What undecidable language $B$ is reducible to its complement?

I encountered a problem which asks to give an example of an undecidable language $B$ such that $B \leq_m \overline{B}$... However, I could find it hard to construct an example ... my difficulty is ...
0
votes
0answers
24 views

planar 1-in-3 sat described as a planar graph for independent set

Given a planar 1-in-3 sat formula, can someone reduce that formula into a graph that asks the question when ever there is an independent set for it, that's also planar?
2
votes
0answers
101 views

Reducing Dominant Set Problem to SAT

I am trying to solve a problem and I am really struggling, I would appreciate any help. Given a graph $G$ and an integer $k$ , recognize whether $G$ contains dominating set $X$ with no more than $k$ ...
1
vote
2answers
770 views

Is NPSPACE also closed under polynomial-time reduction and under log-space reduction?

The complexity classes P, NP, and PSPACE are closed under polynomial-time reduction. The complexity classes L, NL, P, NP and PSPACE are closed under log-space reduction. I wonder if NPSPACE is also ...
1
vote
0answers
54 views

Finding $l$ subsets such that their intersection has less or equal than $k$ elements NP-complete or in P?

I have a set $M$, subsets $L_1,...,L_m$ and natural numbers $k,l\leq m$. The problem is: Are there $l$ unique indices $1\leq i_1,...,i_l\leq m$, such that $\hspace{5cm}\left|\bigcap_{j=1}^{l} L_{i_{j}}...
0
votes
1answer
117 views

Maximum Capacity Path Problem with constraints

I was trying to develop an algorithm for maximum capacity problem with constraints but couldn't figure out the necessary changes required for correct output. The problem is: Given an undirected graph ...
0
votes
1answer
99 views

Show that for every language there exists a harder language

I came across this problem that I could not figure out... For every language $A$, there is supposed to be a language $B$ such that: $$ A \leq_T B $$ but: $$ B \not \leq_T A $$ If it is $A \leq_TB$ and ...
0
votes
1answer
57 views

Variant of Subset-sum has an $O(1)$ algorithm if $Goldbach$ is true

Given $S$ of positive integers $>$ $1$ is there some combination with even $SUM$ > $2$ that is NOT the sum of two primes? $SUM$ = 10 $S$ = $[4,6]$ $No$, Sum of Two Primes $5 + 5 = 10$. ...
1
vote
1answer
188 views

What does "If P1 is reduced to P2, then P2 is at least as hard as P1" mean?

I am having trouble understanding the following statement regarding Turing reduction: "If P1 is reduced to P2, then P2 is at least as hard as P1." Does this mean that (i) P2 can be harder ...
0
votes
1answer
40 views

mapping reductions from R to RE

Let $L_1$ be some language in $R$. Let $L_2$ be some language in $RE$. Is it necessarily that $L_1 \leq_m L_2$ ? I know that for non trivial $L_1$,$L_1$ in $R$ it is right to say that $L_1 \leq_m L_2$....
1
vote
1answer
31 views

proving existence of TM that accepts the next language

I have an idea of how to approach the problem, but I'm not sure about it. Given a Turing Machine, I can check how many states the machine has, and somehow by the number of states to know if the run ...
-1
votes
2answers
175 views

size of intersection of 2 languages size is not decidable

I think that the next language is not decidable but I can't think of reduction to show it. I would appreciate some hint or intuition $EQ = $ { $<M1,M2>$ |$ M1\,\,\, and\,\,\, M2 \,\,\, are\,\,...
1
vote
1answer
183 views

Polynomial-Time reduction from Partition to MakeSpan

Partition Problem: Input: $A:=$ {$a_{1}, ..., a_{n} $}. $a_{i} \in \mathbb{N}$ $\forall i \in$ $\{1, \ldots, n\}$. Question: Exists a subset $A_{1} \subset A$ with: $\sum_{a_{i} \in A_{1}} a_{i} = \...
1
vote
1answer
134 views

Is there a language that cannot be polynomially reduced to?

Is there a language A that cannot be polynomially reduced to by some language B? Or is it always possible to reduce a language B to A?
0
votes
1answer
299 views

How to prove NP-Completeness of longest path between two vertices relying Hamilton NP-Hard problem

I have this question: I have an undirected graph G(V, E) (where V = set of vertices, E = set of edges). Consider the maximum path between two vertices s and t: ...
-1
votes
1answer
108 views

Close To Cook Reduction given NP != coNP

I am struggling to answer these two questions: Prove or wrong: Both are given the assumption that NP != coNP. For any 2 decision problems S, S', if there is a Cook reduction from S' to S then there ...
4
votes
1answer
8k views

Reduction of 3-SAT to Vertex Cover?

Can someone explain to me in the simplest possible way, how to reduce $3SAT$ to $Vertex\:Cover$? I am following the explanation here (scroll to the bottom of page 4). I understand the basic setup of ...
1
vote
1answer
62 views

Solving subgraph isomorphism in polynomial time

So I am a bit confused about the reduction between SAT, subgraph isomorphism (SI) and graph isomorphism (GI). I know that GI is in NP, and that SI is NP-complete. So I'm thinking if we can decide ...
4
votes
2answers
709 views

Can 3-coloring be reduced to 3-clique?

I'm a slight disagreement with my professor over whether or not a certain reduction is possible. He asked us to reduce the problem of 3-Coloring to the problem of 3-Clique. The problem is that I'm ...
1
vote
1answer
43 views

Log space reduction from STCONN to CYCLE

I read this post: Showing Cycle is NL-complete?, but I am not sure why the reduction is log space, as it requires keeping track of the new graph, which has $n^2$ nodes.
2
votes
1answer
504 views

Reducing independent set to triangle-free subgraph

The INDEPENDENT-SET problem is a well-known NP complete problem that takes in a graph $G$ and an integer $k$. It returns true if $G$ has an independent set of size $k$. An instance of the TFS (...
4
votes
1answer
398 views

Why is Graph Isomorphism downward self reducible?

To say that graph isomorphism is downward self reducible means the following: There is an algorithm which decided graph isomorhpism for two given graphs of n vertices in polynomial time by accessing ...
0
votes
1answer
13 views

Can we use the same reduction L1 -> L2 for coL1 -> coL2

does L1 ≤ p L2 yield that coL1 ≤ p coL2 for the same reduction?
1
vote
1answer
67 views

Reducibility of 2 boolean satisfiability problems

I beg some help with this problem. There are 2 boolean satisfiability problems. Problem $A$: Determining whether an arbitrary formula of size $n$ is $satisfiable$. Problem $B$: Determining ...
1
vote
1answer
210 views

Reduction from $HALT$ to $A_{TM}$

I know the reduction to from $A_{TM}$ to $HALT$. But is the following reduction from $HALT$ to $A_{TM}$ correct? We are looking for total computable function $f$ mapping from $HALT$ to $A_{TM}$. The ...
1
vote
1answer
68 views

Turing reducibility of 2 versions of the satisfiability problem

I need help with this problem. There are 2 versions of the satisfiability problem: [1] decision version: determine whether an arbitrary formula f is satisfiable or not [2] search ...
2
votes
1answer
30 views

NPC PROBLEM minimum sum of vertex coloring

For a graph G and a legal vertex-colouring ψ : V(G)→N of G, let σψ(G) be the sum of ψ(v), and set σ(G):=min σψ(G), where the minimum ranges over all valid vertex colourings of G. Prove that {(...
0
votes
1answer
108 views

A non-polynomial reduction

Given two problems $P_1$ and $P_2$. $P_1$ is NP-complete in the strong sense and we want to prove that $P_2$ is also NP-complete but the reduction from $P_1$ to $P_2$ is not polynomial. Can we say ...
1
vote
1answer
108 views

Karp reduction from optimization problems to decision problems

When you consider Cook reductions, then decision and optimization versions of the problems are polynomial time reducible to each other. Focusing on Cook reductions, there exists a natural Karp ...
1
vote
0answers
79 views

Prove that $\#k-colouring$ graph problem is $\#P-complete$

I need to prove, that the $\#k-colouring$ graph problem is $\#P-complete$. I want to construct the reduction from $\#3SAT$ problem, so $\#3SAT \leq \#k-colouring$. The reduction between the counting ...
16
votes
2answers
3k views

Poly-time reduction from ILP to SAT?

So, as is known, ILP's 0-1 decision problem is NP-complete. Showing it's in NP is easy, and the original reduction was from SAT; since then, many other NP-Complete problems have been shown to have ILP ...
2
votes
1answer
94 views

Scheduling to minimize the truncated gaps

I have a single job of unit length, a set of $n$ slots, and a budget of $B$ units. If the job is scheduled at slot $t$, then it will consume $c(t)$ units of the budget $B$. If the job is not scheduled ...
0
votes
0answers
19 views

Computing Every Path from a Source to Multiple Destinations [Simpler Algorithm]

How are these two problems different? I. Find all paths between a source vertex and destination vertex. II. Find all paths between a source vertex and all vertices in the graph. Both of these ...

1 2 3
4
5
23