Questions about finding mappings between problems that allow solving one problem using a solution of another one.

learn more… | top users | synonyms

1
vote
1answer
8 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 ...
1
vote
1answer
37 views

How to build the Reduction from Hamiltonian Cycle problem to Subgraph isomorphism? [duplicate]

I'm trying to prove that the Subgraph isomorphism problem is NPC using the Hamiltonian Cycle problem. Unfortunately I feel (or don't understand) that the solution is "empty" and doesn't explain the ...
1
vote
1answer
28 views

L closed under logspace reduction

Given two languages $A$ and $B$ I have been asked to show that, if $B \in L$ and we have a logspace reduction $f$ from $A$ to $B$ then $A \in L$. I read the proof that $L$ is closed under logspace ...
4
votes
0answers
41 views

Turing reductions by NX ∩ coNX and binary relation problems

Let $A$ be a non-deterministic algorithm computing a binary relation between an input string and possible output strings. Let NX be a (potentially non-deterministic) complexity class. What is a good ...
1
vote
1answer
35 views

How exactly does a Max 2 Sat reduce to a 3 Sat?

I've been reading this article which tries and explains how the max 2 sat problem is essentially a 3-sat problem and is NP-hard. However, if you see the article, I'm not able to understand why, after ...
4
votes
1answer
227 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 ...
3
votes
1answer
37 views

Is the following language recursively enumerable?

Let $L =\{ <M> | $ the amount of words $w\in\Sigma^*$ that $M$ does not halt on is finite $\}$. I would like to prove that $L\notin RE$. I can show that $\overline{L}\notin RE $ that is ...
1
vote
0answers
36 views

Poly-time reduction from directed Hamiltonian Path to undirected HP, both with with known start and end

this is homework, so PLEASE do not give me the solution(!), but help me get there on my own. I've got to proof that directed Hamilton Path with fixed stard and ending and undirected Hamilton Path ...
4
votes
1answer
29 views

Reduction from ATM to ATM-complement

Is there a reduction from ATM to ATM-complement? (ATM denotes the language $\{\langle M,w \rangle \mid \text{TM $M$ accepts $w$}\}$) I have been thinking about it too much and couldn't find the ...
4
votes
1answer
43 views

Can we use reductions to design approximation algorithms for NP-hard problems?

Let us say that I have a problem $P(n)$ that I need to solve (where $n$ is the size of the input of problem $P$). I used a polynomial-time reduction from a known NP-hard problem $Q(m)$ (where $m$ is ...
1
vote
0answers
19 views

Reduction of decidable and undecidable problems [closed]

Let: f be a decidable decision problem. g be an undecidable decision problem. I refered to those rules: If $f$ reduces to $g$ and $g$ is decidable $\implies$ $f$ will be decidable. If $f$ ...
0
votes
1answer
58 views

Does exponentiation reduce to multiplication or the other way around?

Is is more accurate to say that in complexity theory: $$\text{exponentiation} \leq_p \text{multiplication}$$ or $$\text{multiplication} \leq_p \text{exponentiation}$$ I understand that if we know ...
3
votes
1answer
56 views

How to show that a problem is easy?

Let $P$ be a problem that you need to study its difficulty, i.e., NP-hard, Polynomial-time solvable, etc. My question is: If I reduce a known polynomial time problem (say, maximum matching in ...
5
votes
2answers
216 views

Is the set of TMs that does not reach most cells to the right computable?

Let $L_{NTF} = \{ \langle M \rangle \mid $ for every $x\in\Sigma^* $ the machine $M$ does not reach the $|x|+10$'th cell during its calculation on $x$. $ \}$. I would like to prove or disprove ...
4
votes
1answer
38 views

How to prove the following language is not in R

Let $c\in \mathbb{N}$. Denote: $L _c= \{ \langle M \rangle \mid \exists _{U \subseteq \Sigma ^* }$ s.t. $|U| $ is infinite and for each $w\in U $ the TM $M$ accepts $w$ within no more than $c$ steps ...
1
vote
1answer
13 views

Reduction from $A_{TM}$ to Rice theorem: what if input of $A_{TM}$ loops?

I'm learning this reduction from $A_{TM}$ to $R_P$ for the proof of Rice's theorem. This is the reduction: https://gyazo.com/10cdc3b833a8d1bd9cdbb1eb08e76303 (Source of the slides: The University of ...
0
votes
1answer
51 views

IF A is reduced to B and B belongs to NPC then where does A belongs to?

i came across a question with no proper explnation. IF A is reduced to B and B belongs to NPC then we cant say anything about A since it can be as harder a NPH and as easier as P. i know why it is as ...
0
votes
0answers
23 views

Is there a general form of polynomial reductions in complexity theory? [duplicate]

While reading Sipser, in computability I read about many to one mapping reducibility and Turing reducibility,the latter one being a more general form of reducibility. But in the introductory chapter ...
-1
votes
0answers
38 views

Conditions on randomized reductions

Supposing we have a problem $\Pi$. Suppose $\Pi$ has a randomized reduction from $\mathsf{3SAT}$ but there is no deterministic reduction then it is clear $\mathsf{NP}\neq\mathsf{P}$. My query is ...
1
vote
1answer
49 views

Showing a problem is NP complete? Reducing CLIQUE to KITE.

I've got an exam next week all about this sort of thing. Ie: Find polynomial certifier for a problem, give a polynomial reduction, prove problem X reduces to Y and etc. The problem is, there doesn't ...
-1
votes
1answer
97 views

How can one reduce 3-CNF-SAT and k-CNF-SAT to each other?

I am studying for NP problems. To prove k-CNF-SAT is NP-hard, there must exists something that can be reduced to k-CNF-SAT. So what I thought is to reduce 3-CNF-SAT to k-CNF-SAT and reduce k-CNF-SAT ...
1
vote
1answer
34 views

Reduce Min-Cut to 0/1 Integer Program

Given an undirected, weighted graph $G=(V,E)$ and two nodes $s,t \in V$ and weight function $w: E \rightarrow \mathbb{N}$. The weight of a (s,t)-cut $ (U, U^C)$ is given by: $$ w(U,U^C) := ...
0
votes
0answers
98 views

Reduction from 3-Partition to a cutting problem

My problem is the following: Input: a set of $m$ non-negative integers $\{b_1,...,b_m\}$ and a parameter $n$ with $n<m$. Output: $n$ sets of 3 numbers Task: Cut the $b_i$'s into $3n$ integers ...
0
votes
0answers
36 views

In computer science, is there a term that describes a solution set that is guaranteed to contain the solution to a NP hard problem?

Suppose that a NP hard problem involves finding a set $A$, and that there exists a polynomial time algorithm that is able to find a smallest set $B$ such that $A \subset B$. Occasionally, we might be ...
1
vote
1answer
46 views

what does “reduce A problem to B problem in polynomial time” mean? [closed]

It is kind of NP-complete problem. For example, A problem: Given a sequence of numbers, return the maximum value within these numbers. B problem: Given a sequence of numbers, return start index ...
4
votes
1answer
61 views

Machines whose languages are their own encoding

Is the language $S = \{\langle M \rangle \mid M \text{ is a Turing Machine and } L(M) = \{\langle M \rangle\}\,\}$ decidable, recognizable and/or co-recognizable? I tried diagonalization but can only ...
1
vote
1answer
60 views

Do polynomial reduction functions work both ways?

For example to prove 3-Sat ≤p Independent Set do I just have to prove this theorem: Theorem- Formula F is satisfiable IFF graph has an independent set. If I have to prove it this way does this also ...
1
vote
1answer
41 views

NP-complete reduction for a k-dumbbell graph

A k-dumbbell is a graph that consists of 2 cliques each of size k with one and only one edge between them. How do I show that finding if a graph is a k-dumbbell is NP-complete? Proof it is in NP: ...
1
vote
1answer
64 views

NP to SAT. How does it works? [closed]

Let's start here: It is said that all NP problems can be reduced to SAT(boolean satisfiability problem). To be more accurate to Circuit SAT, because all decision problems like NP should end up with ...
0
votes
0answers
35 views

Is NP-hardness closed?

Let $X\leq Y$. If $X$ is $NP$-hard, is $Y$ $NP$-hard? I think yes, as if an $NP$ problem is reducible to $X$ in polynomial time, then surely it is also reducible to $Y$ given that $X\leq Y$. If $Y$ ...
1
vote
0answers
18 views

NP-Complete: reduce “L” the language such as circuits C1 and C2 compute the same function

I'm trying to reduce the NP-Complete language "CIRCUIT-SAT" (C is a boolean circuit that is satisfiable) to my language L, but my classmates are pointing out that i'm actually doing the opposite, ...
-2
votes
1answer
79 views

Reduction from 3SAT [closed]

You are given a directed acyclic graph G = (V, E) in which each node has one “left” out-arc and one “right” out-arc, with a distinguished source node s and sink node t. You are also given a list of ...
0
votes
0answers
50 views

Polygon casting - Removing from mold by rotation

How can I show that the problem of finding a center of rotation that allows us to remove P with a single rotation from its mold can be reduced to the problem of finding a point in the common ...
0
votes
1answer
29 views

Finding subset such that one sum is more than target and another sum is less

Consider the following problem: Given positive integers $a_1,\ldots,a_n,b_1,\ldots,b_n,A,B$, does there exist a subset $S$ of $\{1,\ldots,n\}$ such that $\sum_{i\in S}a_i\geq A$ and $\sum_{i \in ...
2
votes
1answer
44 views

Proving “QUESTION” is NP-Complete by reduction from n-variable 3SAT [duplicate]

I'm struggling with a problem in my theory of computation course that asks us to prove "QUESTION" is NP-complete by reduction from n-variable 3SAT. I've done a number of other similar reductions but I ...
1
vote
1answer
75 views

DFA accepts common strings, reduction to NPcomplete

$B=\{\left<M_1,M_2,...,M_k\right>\text{ : Each $M_i$ is a DFA and all of the $M_i$ accept some common string.} \}$ I'm trying to show that B is NP-complete. I know I have to reduce it to ...
6
votes
1answer
59 views

What NP decision problems are not self-reducible?

So we just learned about self-reducibility in class. My professor and our textbook would not commit to saying that all problems in NP are self-reducible, but there didn't seem to be any examples of ...
4
votes
2answers
149 views

What is an “encoding” of a TM?

I'm currently working on a reduction from $A_{TM}$ to another language, and have been reading through some example proofs. I've come across the situation where, for example, we have $L = \{ \langle ...
2
votes
1answer
82 views

Approximate Subset Sum with negative numbers

I am interested in the approximation version of the Subset Sum problem with negative numbers. Wikipedia says there is an FPTAS algorithm for SS. That Wikipedia page states: If all numbers are ...
1
vote
1answer
69 views

Language Reduction for any Language

Given two languages $L_1$ and $L_2$, give a language $L'$ that both $L_1$ and $L_2$ reduce to. I'm not quite how to do this. I know the solution is fairly simple. I know I can somehow represent $L'$ ...
2
votes
1answer
87 views

Mapping reducibility vs. Turing reducibility

Let $A$ and $B$ be two languages. If $A \le_{m} B$ ( reducible by mapping ) then I know that if $B$ is decidable so is $A$ and if $B$ is recognizable so is $A$. And if $A \le_{T} B$, then if $B$ is ...
-3
votes
1answer
50 views

Reduction from deciders of the universal to deciders of the empty language

$ALL_{TM} = \{\langle M\rangle | \; M$ is $TM$ and $L(M)=\Sigma^*\}$ $E_{TM} = \{\langle M\rangle | \; M$ is $TM$ and $L(M)=\emptyset\}$ I can't find reduction of $ALL_{TM}$ to $E_{TM}$. But I ...
0
votes
1answer
46 views

Subset-sum variation, multiple sums

Subset-sum problem is NP-complete. I presume so is the problem of determining, given a positive integer $p$, whether in a set of positive integers $\{x_1,x_2,...,x_n\}$ there is a subset which sums to ...
1
vote
1answer
84 views

$\mathbf{NC_2}$ is closed under log-space reduction

I actually have to prove the following : $\mathbf{NL} \subseteq \mathbf{NC_2}$ I have the following approach : I will prove that $\mathbf{PATH} = \{〈D, s, t〉 | \text{D is a directed graph with a ...
-2
votes
1answer
33 views

What NP-complete problem to reduce to k-Edge-Colorability to prove its NP-hardness?

What known NP-complete problem would one reduce to $k$-Edge-Colorability to prove that the latter is NP-hard?
7
votes
1answer
283 views

NP-hardness of covering with rectangular pieces (Google Hash Code 2015 Test Round)

The Google Hash Code 2015 Test Round (problem statement) asked about the following problem: input: a grid $M$ with some marked squares, a threshold $T \in \mathbb{N}$, a maximal area $A \in ...
0
votes
0answers
41 views

Turing machine M overwrites a non-blank char by B (Blank)?

What are the implications of a non-blank character being over-written by a Turing machine M for the given input variable 'x'? Intention of the question: I am trying to answer how the halting ...
4
votes
1answer
56 views

Machine with an oracle for a language that cannot decide another language in polynomial time

We usually see examples of languages contained in $P^A$ for some language $A$, or cases where $P^A=P^B$ (or $P^A\subseteq P^B$) for two languages $P^A$ and $P^B$. However, there is any explicit ...
1
vote
1answer
40 views

Proof that circuit design problem is NP-hard [closed]

I have the following problem, and I want to show that it is NP-hard (or NP-complete). Consider a clause which can have OR and XOR relationship between literals, e.g. $c_1=y_1 \lor y_2 \lor (y_3\oplus ...