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

learn more… | top users | synonyms

2
votes
2answers
47 views

Showing that deciding whether a given TM accepts a word of length 5 is undecidable

I'm having trouble grasping this the concept of reductions. I found the solution and it looks like this: Assume that $M_5$ is a Turing Machine that can decide if a given Turing Machine $M$ accepts ...
1
vote
1answer
14 views

If A is mapping-reducible to B and is not mapping-reducible to co-B, is A Turing-reducible to co-B?

If $A \leq_m B$ and $A$ is not mapping reducible to $co\text{-}B$, then $A \leq_T co\text{-}B$. Is this true? My intuition is false even if we can find some special case to make it true such as ...
1
vote
1answer
45 views

3-SAT to Max-2-SAT Reduction

I'm trying to find reduction from 3-SAT to Max-2-SAT, so far no luck. Let me first describe it. 3-SAT: Given a CNF formula $\varphi$, where every clause in $\varphi$ has exactly 3 literals in ...
1
vote
1answer
45 views

Showing that DNF VALID is coNP-hard

I'm trying to understand/show that DNF VALID is coNP-hard. I have given an algorithm for the complement of DNF VALID and shown that this is in NP (since the complement of a language in NP is in coNP), ...
-1
votes
1answer
25 views

3SAT to CNF-SAT reduction

I am trying to prove that 3SAT is polynome time reducable to CNF-SAT, but I don't know how to do this. A formula F is in 3SAT iff f(F) is in KNFSAT, but since 3SAT is a part of KNFSAT, every formula ...
0
votes
1answer
22 views

Reduction from Partition problem to 3-Partition problem

I'm trying to show how to reduce the Partition problem to the 3-Partition problem. I'll first describe the problem using the definitions and notations I'm familiar with (I hope they're legit), and ...
5
votes
0answers
49 views

Reduction from clique to bag automata

I am trying to figure out a reduction to prove $W[1]$-hardness for this, but I am having significant trouble. Here is the problem: Bag Automaton: A non deterministic finite state automaton ...
3
votes
1answer
36 views

Polynomial Reduction 3SAT to K-Clique

I am reading the reduction given by Sipser in his textbook "Introduction to the Theory of Computation," on page 303. The reduction is: \begin{equation} 3SAT \leq_p KCLIQUE \end{equation} I am really ...
-1
votes
1answer
45 views

SAT reduction to prove NP completeness [closed]

Suppose you have a set of binary strings of length n, the magnitude of a string is the number of 1's it has. and you want the program to return true if there is a string of length n that has a ...
2
votes
1answer
85 views

Log-Space Reduction $CO-2Col \le_L USTCON$

I want to show that $CO-2Col \le_L USTCON$ (Log-Space reduction) $USTCON$ The $s-t$ connectivity problem for undirected graphs is called $USTCON$. [Input]: An undirected graph $G=(V,E)$, ...
0
votes
1answer
48 views

P, NP and polynomial time reduction?

If $P = NP$ would this imply that polynomial time reduction from an $NP$- to a $P$-problem would be possible? And if $P\neq NP$ does it imply that a polynomial time reduction from an $NP$- to a ...
1
vote
2answers
75 views

Does a polynomial-time reduction from A to B imply that B is in NP if A is?

Let f be a polynomial-time reduction of a decision problem A to a decision problem B. We know that, if B $\in$ P then A $\in$ P. Similarly, if B $\in$ NP then A $\in$ NP. However, what about the other ...
5
votes
1answer
138 views

Reduce Vertex cover to SAT

I need to reduce the vertex cover problem to a SAT problem, or rather tell whether a vertex cover of size k exists for a given graph, after solving with a SAT solver. I know how to reduce a 3-SAT ...
0
votes
0answers
10 views

Show polynomial hierarchy levels closed under reduction [duplicate]

Most books assume that this is obvious, but I can't see how each $\Sigma_k=NP^{\Sigma_{k-1}}$ level in the polynomial hierarchy is closed under polynomial-time reductions. Is there something that I'm ...
-1
votes
2answers
24 views

Proving that Max Weighted Independent Set is in NP

What I'm trying to do is to show a problem in NP can be reduced to the min weight vertex cover problem I've chosen the max independent weight problem = input: A graph G with weights on each vertex, ...
1
vote
2answers
73 views

Every language that is reducible to a language in $\Sigma_i^p$ is also in $\Sigma_i^p$ . How?

The complexity class $\Sigma_{k}^{p}$ is recursively defined as follows: \begin{align} \Sigma_{0}^{p} & := P, \\ \Sigma_{k+1}^{p} & := P^{\Sigma_{k}^{p}}. \end{align} Why is every language ...
0
votes
1answer
96 views

Relaxed graph coloring, with penalties for assigning adjacent vertices the same color

Consider a set of $N$ nodes. There is a $N\times N$ non-negative valued matrix $D$ where the $(i,j)$th element $d_{ij}$ gives the "positive metric" between node $i$ and $j$, where $i,j\in [N]$. Thus ...
2
votes
1answer
92 views

Proving NP-completeness of a graph coloring problem

Given a graph $G=(V,E)$ and a set of colors $k<V$. Find a assignment of colors to vertices that minimizes the number of adjacent vertices in conflict. (Two adjacent vertices are in conflict if they ...
1
vote
1answer
24 views

There is equivalence in an NP-hardness proof or not?

I want to show that some problem $P_1$ is NP-hard. I have a problem $P_2$ that is NP-complete. From an instance of $P_2$ I created in polynomial time an instance of the problem $P_1$. My question is: ...
3
votes
2answers
41 views

How to write a many-one reduction proof

Writing a proof by contradiction is fairly formulaic--first you assume the opposite, then derive a contradiction. I would like to know the steps and conventions for writing a many-one reduction ...
2
votes
1answer
57 views

Reducing 3SAT to Triangle Cover Graph

The Triangle Cover Graph problem is this: Given a graph $G = (V,E)$ and an integer $k$, does there exist a set of at most $k$ vertices of $G$ such that every triangle contained in $G$ also ...
1
vote
1answer
64 views

Is this path finding problem in a 01-matrix NP-complete?

The problem: Input: An $n \times n$ matrix of 0's and 1's, and a position pos of this matrix (i.e. a pair of integers $i,j$ with $1 \leq i,j \leq n$) Output: YES if there exists a ...
3
votes
0answers
43 views

What is an upper bound on formula size when converting 3-SAT to UNIQUE 3-SAT?

What is an upper bound on formula size when converting 3-SAT to UNIQUE 3-SAT? We can use the Valiant Vazirani Therom, also found here (in more detail). Essentially, it is a randomized algorithm that ...
2
votes
2answers
111 views

Proving iff statement with reductions

I have a statement I am trying to prove, and I'm very close, but I think I'm missing a couple of key concepts about regular and context-free languages. Question: Let $ A = \{ ww \ | \ w \ \epsilon \ ...
1
vote
1answer
85 views

Reduction to complement of Accept Problem

I am reducing a given Turing Machine to the complement of the known undecidable problem, $$ Complement(A_{TM}) = \{ \langle M,w \rangle \mid M \text{ is TM}, w \not\in L(M) \}$$ To this Turing ...
0
votes
0answers
29 views

A two way Mapping reduction

There's something in my class notes i don't understand, if anyone here could clarify it would be great. Given a mapping reduction from A to B that's Injective and Surjective, if B is in ...
-1
votes
2answers
41 views

Reducing 3CNF to Clique: Why do we omit negated literals?

I have an example for a reduction of 3CNF to Clique, there is one thing I don't get about it, hopefully you could clarify it. The reduction works like this: Construct a graph G = (V, E) as ...
5
votes
1answer
65 views

Can we construct a Karp reduction from a Cook reduction between NP problems?

We have had several questions about the relation of Cook and Karp reductions. It's clear that Cook reductions (polynomial-time Turing reductions) do not define the same notion of NP-completeness as ...
2
votes
3answers
100 views

Is the set of programs that compute some function other than $h$ recursively enumerable?

Let $h$ be a total computable function. Is $S = \{x \mid f_x \neq h\}$ recursively enumerable? Originally this was an exercise that restricted $h$ to: $h(x) = x + 1$ . However, it can be ...
2
votes
1answer
62 views

0/1 Integer Programming and Karp's Reduction

I have been reading Karp's famous paper on the NP-Completeness of different problems, Reducibility among combinatorial problems, and I have a question on the reduction from SAT to 0/1 Integer ...
1
vote
0answers
35 views

Is this reduction done correctly? [closed]

So we have two problems: Problem A: Given a list of positive integers, decide whether the list contains a subset adding to a given number t. Problem B: Given a list of integers, decide whether the ...
-1
votes
2answers
83 views

Can $\emptyset$ be reducible to any other language? [duplicate]

While solving some question, that involved the empty set $\emptyset$, I was really wondering, is $\emptyset$ reducible to any other language, i.e., $\emptyset \leq A$ such that $A$ is a language over ...
2
votes
1answer
64 views

Reduction between $\Sigma^*$ and $\emptyset$

Throughout the subject of reductions, I was wondering: If we take $L_1 = \Sigma^* $ and $L_2 = \emptyset$, is $L_1 \leq L_2$? is $L_2 \leq L_1$? What I mean is, Is there some sort of reduction ...
5
votes
2answers
125 views

Can one reduce a problem of unknown complexity to a hard problem to show hardness?

In this paper (page 3 Theorem 1) the authors want to prove that their problem is NP-complete. Their method is as follows. Let their problem be known as $P$. They show that their problem can be written ...
0
votes
1answer
41 views

Using approximations to optimization problems for threshold problems

Many problems in computer science come in two flavors: Optimization problem: "Find an object with the largest size". Threshold problem: "Given $n$, find an object with a size of at least $n$, or ...
0
votes
1answer
95 views

Does two languages being in P imply reduction to each other?

Given two languages $L_1$ and $L_2$ that are in $\mathsf{P}$, can it be proven that there is a polynomial time reduction from $L_1$ to $L_2$ and vice versa? If so, how? I noticed that if $L_1$ is the ...
10
votes
0answers
124 views

Graph problem known to be $NP$-complete only under Cook reduction

The theory of NP-completeness was initially built on Cook (polynomial-time Turing) reductions. Later, Karp introduced polynomial-time many-to-one reductions. A Cook reduction is more powerful than a ...
0
votes
2answers
62 views

Mapping reduction to show NeverHalt is undecidable

I need help with showing that $$NeverHalt_{TM} = \{\langle M\rangle \mid \text{$M$ is a TM which runs forever on every input $w$}\}$$ is undecidable by giving an explicit mapping reduction. To show ...
5
votes
1answer
85 views

Approximation algorithms for NP-complete problems

Given two NP NP-hard functional problems, A and B, one can find a reduction of A to B. Is it possible to find a reduction that would honour approximations? That is, if you have an approximation ...
1
vote
1answer
54 views

Reducing from a Turing machine that recognizes is regular to the halting problem

I'm trying to understand reduction, this is from my textbook and is not a homework problem or even any exercise, just trying to understand an example they present. This is the reduction they give: ...
4
votes
1answer
84 views

Proving SSum is NP-Complete?

SSUM is the same as the Subset Sum Problem with the only additional requirement is all the numbers must be unique in the subset. To prove it's NP complete, the verifier is quite easy to construct ...
1
vote
2answers
74 views

Turing machine which diverges on its own code

Show that the set $K^{c}$ = $\lbrace M \mid M(M) \text{ diverges} \rbrace$ is not recursively enumerable. This question is essentially asking to show that the set of turing machines which diverge ...
2
votes
1answer
256 views

Question on SAT reduction

Let Two-Solutions-SAT be the language of Boolean formulas that have exactly two distinct satisfying assignments. Show Two-Solutions-SAT is co-NP-hard. I know how to show that the complement of ...
3
votes
1answer
83 views

Find subset with minimal sum under constraints

Let $M$ be a finite set of even cardinality. Define $C=\{\{a,b\}:a,b \in M, a \neq b\}$ the set of all pairs over $M$. Let $w:C \rightarrow \mathbb{R}^+_0$ be a function. Now find $C' \subset C$ with ...
3
votes
1answer
61 views

CNF SAT conversions

I am interested in reductions from 3-CNF boolean expressions to similar restricted forms. For example, I am interested in knowing how to reduce a 3-CNF formula to another 3-CNF formula where each ...
1
vote
0answers
72 views

Tips for showing a language is NP-Complete [closed]

I understand and know how to show that a language B is NP-Complete. Show that $B\in NP$ Show that every language $A\in NP$ is polynomial time reducible to $B$ For step 2, it is sufficient to give ...
0
votes
0answers
85 views

Reduction to maximum clique

What is a polynomial reduction to the maximum clique problem of the following problem Given a set of n axis-aligned rectangles in the plane, how big is the largest subset of these rectangles that ...
1
vote
1answer
87 views

Mistake in Karp's paper on NP-Complete problems?

I read on a blog that there are mistakes in Karp's paper where he proved that 0-1 programming is NP-Complete, but I couldn't find it, can anyone explain? And I doubt that there are also mistakes where ...
0
votes
0answers
81 views

reduce hamiltonian cycle to a traveling salesman and hamiltonian path to hamiltonian cycle

I have a really bad professor for my automata class. She is all over the place, except where she needs to be. I have two problems and I don't know how to even start. I know for some of you these ...
0
votes
1answer
48 views

Finding a function which is a mapping reduction of A to B

How do I precisely define the function which is a mapping reduction of A to B for the following examples? What is the process of figuring this out? Given: A and B are languages over the alphabet ...