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
vote
1answer
34 views

how does Kleene-Post show two languages that are not Turing reducible to each other?

I'm having difficulty understanding the proof of the Kleene-Post result. It purports to construct two languages that are not Turing reducible to each other, using a diagonalization argument. I've seen ...
0
votes
1answer
105 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
1answer
17 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?
2
votes
1answer
29 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 ...
0
votes
1answer
51 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 ...
0
votes
0answers
38 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 ...
3
votes
2answers
87 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 ...
3
votes
0answers
47 views
+50

Reduction from 3-partition to ABC-partition

The ABC-partition problem is a variant of 3-partition in which, instead of a single set $S$ with $3 m$ positive integers, there are three sets $A, B, C$ with $m$ positive integers in each. The goal is ...
2
votes
0answers
74 views

3-partition problem without the restriction to triplets

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 ...
1
vote
0answers
12 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
125 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 ...
2
votes
1answer
84 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 ...
-2
votes
1answer
69 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
33 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 ?
0
votes
0answers
25 views

About the complexity of deciding if the closed world assumption for renamable Horn CNF is consistent

Let $T$ be a theory that only contains renamable horn formulas. What is the complexity of deciding if the closed world assumption $CWA(T)$ is consistent? The closed world assumption is defined as ...
1
vote
1answer
71 views

Is protein folding NP-hard and how to prove that?

This question has two facets that are related. Is the general problem of protein folding really NP-hard? The hydrophobic-polar protein folding model (Ken Dill et al., 1985) stated the problem on a ...
0
votes
0answers
22 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?
0
votes
1answer
60 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 ...
2
votes
0answers
28 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$ ...
0
votes
0answers
11 views

Does $L \leq_p K$ and $K\in NP$ implies $L \in NP$?

I only find theorems like $L \leq_p K$ and $K\in P$ implies $L \in P$ in books, but I think the same should be true for NP as well. Or is there anything I am missing? I am asking since this would be ...
1
vote
0answers
52 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
38 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
22 views

reduction of independence problem and cluster problem

independent problem is: there is a simple and undirected graph, we are looking for the maximum vertex in which there is no edge between any two of them. cluster problem is: there is a simple and ...
0
votes
1answer
31 views

Problem with proving that $RP \subseteq NP$ : a non-deterministic TM for a language $L \in RP$

I'm having a small issue with wikipedia's proof that $RP \subseteq NP$: An alternative characterization of RP that is sometimes easier to use is the set of problems recognizable by nondeterministic ...
0
votes
1answer
54 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
48 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
24 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
30 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
81 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
64 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} = \...
0
votes
0answers
16 views

Redcue CFG-Eequiv to CFG-SYM [duplicate]

I want to show, that for an CFG G the question wether $L(G)=L(G)^R$ is undecidable. My first try was to reduce from the CFG-Equivalent Problem) $CFG_{EQUIV}\leq CFG_{SYM}$. My first attempt was to ...
0
votes
1answer
64 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
75 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 ...
0
votes
1answer
49 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
2answers
118 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 $...
4
votes
2answers
509 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 ...
0
votes
0answers
16 views

Translating running times of $3$-coloring to $k$-$SAT$ complexity

Suppose there is an $O(f(n))$ algorithm for $3$-coloring a graph on $n$ vertices what does it translate to in terms of time complexity for solving $k$-$SAT$ with $m$ clauses?
1
vote
1answer
21 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.
1
vote
1answer
51 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 (...
0
votes
1answer
12 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
39 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
65 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 ...
1
vote
1answer
62 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 ...
2
votes
1answer
25 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 {(...
1
vote
1answer
44 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 ...
0
votes
0answers
14 views

Search reduction to decision

I'm a little stumped on this question (and I don't know the name of it, which is why I've excluded it from the title). I need to describe an algorithm that finds a solution to an NP-Hard problem given ...
1
vote
0answers
55 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 ...
0
votes
0answers
17 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
vote
1answer
36 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 ...
0
votes
1answer
39 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}$. ...

1
2 3 4 5
21