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

learn more… | top users | synonyms

1
vote
0answers
5 views

Finding a perfect matching using an LP

I have a basic question about the power of Linear Programming that has been bothering me for some time. I believe there is something simple I am missing. Linear Programming is $\mathsf{P}$-complete, ...
1
vote
1answer
50 views

Finding a pair of edge disjoint paths in a graph, such that the weight of each of them is bounded

Given an undirected graph $G=(V,E)$, two distinct vertices $s,t\in V$, a weight function $f:E \to \mathbb{N}$, and a constant $M\in \mathbb{N}$, does there exist a pair of edge disjoint paths ...
0
votes
1answer
39 views

Clarification of Hopcroft's proof that “deciding whether a program halts on all inputs” is not R.E

$DoesNotHaltOn\_w=\{(M, w) : M$ does not halt on input w$\}$ $AlwaysHalt =\{ M : M$ halts on all inputs x $\}$ Hopcroft gives the following proof that $AlwaysHalt$ is not R.E. 1) Given an input ...
-1
votes
0answers
32 views

Follow-up question to: Problems that ask whether a language is R.E

$L = \{P : P(n)$ outputs $n^2$ for all $n \in N\}$ $TOTAL=\{P : P(n)$ halts on every input $n \in N \}$ In a previous post, I asked whether "outputs" meant "halts and outputs". The response was ...
5
votes
2answers
73 views

Exponential-size numbers in NP completeness reduction

In the proof of Theorem 4 in [GS'12], the authors reduce an instance of PARTITION to their problem. Therefore, they create for each element $a_i$ in the instance of PARTITION a number $2^{c \cdot ...
-2
votes
0answers
23 views

Prove that VC (Vertex Cover) is in NP [duplicate]

I have this question in which it states that I have to prove whether Vertex Cover is in NP. I'm trying to understand my notes but the problem is that I do not know whether this is actually valid I ...
1
vote
1answer
63 views

Reduction to Maximum Independent Set

Suppose you had a set $P$ of people. Every person $p_j \in P$ is familiar with atleast one other person $p_i$ (familiarity is symmetric). Is there a subset $S$ of people such that for $|S| \ge k$, no ...
-2
votes
1answer
32 views

Why does reduction from vertex cover to subset sum use base-4? [closed]

Why does reduction from vertex cover to subset sum use base-4? 30.13 Subset Sum (from Vertex Cover)
2
votes
1answer
66 views

Reduce Set problem to SAT

So the problem is, given some set $M = \{x_1,x_2,\ldots,x_n\}$ and a set of subsets $S = \{S_1, S_2, \ldots, S_m\}$ where $S_i \subseteq M$. We want to find some set $X \subseteq M$ such that $|X| \le ...
3
votes
1answer
59 views

A Reduction from XORSAT to 2-SAT

Does anyone know of a non-trivial reduction from XORSAT to 2-sat since they are both in P? (By non-trivial I mean one that does not just solve the instance of XORSAT and map it to a fixed instance of ...
1
vote
1answer
37 views

A detail on variant of Mahaney's theorem about reductions of sparse languages vs P/NP

Wikipedia states on sparse languages that There is a Turing reduction (as opposed to the Karp reduction from Mahaney's theorem) from a NP-complete language to a sparse language iff NP $\subseteq$ ...
0
votes
1answer
52 views

Why is $A_{TM}$ reducible to $HALT_{TM}$?

In Sipser, there is a proof I don't understand. First he established the undecidability of $A_\mathrm{TM}$, the problem of determining whether a Turing machine accepts a given input. ...
0
votes
0answers
55 views

Reduction to the constrained-shortest-path problem (CSP)

How can I reduce the subset sum problem to the CSP? Is this possible ? There are quite a few formulations of the CSP, I am talking about the following: We have an s-t graph, whose edges have costs and ...
6
votes
0answers
46 views

What do complexity classes look like, if we use Turing reductions?

For reasoning about things like NP-completeness, we typically use many-one reductions (i.e., Karp reductions). This leads to pictures like this: (under standard conjectures). I'm sure we're all ...
3
votes
2answers
113 views

Need Help Reducing Subset Sum to Show a Problem is NP-Complete

I want to show that the following problem is NP-Complete: For a set of vectors $v_1,\ldots,v_n \in \mathbb{N}^d$ and an integer $k$, does there exist a subset $S \subseteq \{v_1,\ldots,v_n\}$, such ...
0
votes
0answers
25 views

A polynomial reduction from HAMPATH to LONG-PATH [duplicate]

$\text{HAMPATH} = \{(G=(V,E),s',t')| \text{ G has a Hamilton path from s' to t' } \}$ $\text{LONG-PATH} = \{(G,s,t,k) | \text{G has a simple path p from s to t, length(p) $\geq$ k} \}$ I'm trying ...
3
votes
1answer
44 views

Reduction from PARTITION to MAX-CUT

I am trying to prove the NP-Hardness of the MAX-CUT problem. Other sources seem to reduce from the NAE-3SAT problem, however I have been trying to reduce from PARTITION because PARTITION and MAX-CUT ...
-2
votes
1answer
54 views

NP hard: Mixed Q Horn SAT

Prove that Mixed Quantified Horn SAT problem is NP hard by reducing the Q3SAT problem to it. Q3SAT: 3SAT with possibly universally and existentially quantified variables. Mixed Quantified Horn ...
1
vote
1answer
62 views

Proving DPATH is NP-complete by a reduction from HAMPATH

I have a language DPATH that I'm trying to complete is NP-complete. ...
0
votes
1answer
40 views

Confusion in Reducibility

In Sipser's Theory of Computation book, it is stated while reducing ATM to REGULARTM We let R be a TM that decides REGULARTM and construct TM S to decide ATM. Then S works in the following ...
0
votes
2answers
51 views

Reducing A(TM) to some decidable problem

We know that A(TM) is undecidable, what if we reduce A(TM) to A(DFA) which is decidable? How will we prove that A(DFA) is decidable? I couldn't find an example or theory. Thanks
1
vote
3answers
68 views

NP-completeness: Reduce to or reduce from?

Very simple question, but a mistake I make often enough that I'd love to have a standard reference. I'm showing that a problem $P$ is NP-Hard by assuming I have a polynomial time algorithm to solve ...
1
vote
2answers
45 views

Proving a language is not decideable using a reduction from Busy Beaver?

I was given this function: $F(n)$ returns the smallest TM (measured in number of states) such that on input $\epsilon$, the TM makes at least $n$ steps before eventually halting ($n$ is a natural ...
0
votes
1answer
40 views

Reduction from partition to multiprocessor scheduling

I am kind of unsure about a reduction between two problems. Here are the two problems: PARTITION: Instance: A finite set of n positive integers $S= \{a_1,a_2,...a_n\}$. Question: Can the set $S$ be ...
1
vote
1answer
40 views

What is the difference between turing reductions and many-one reductions?

To show that a particular language $A \in C$ is $C$-complete, where $C$ is some complexity class, we might construct a reduction from some known $C$-complete language $B$ to $A$, where $B$ is ...
0
votes
1answer
35 views

Is polynomial time reducibility reversible?

If a language $A$ is reducible to some language $B$, does it follow that $B$ is reducible to $A$? My guess is no, it having something to do with the function $f$ in the definition of $A$ reducing to ...
0
votes
1answer
198 views

NP Completeness of 3-SAT problem [closed]

I have started reading on algorithmic complexity for my thesis work. Already have studied on Polynomial time reducibility, NP-Complete, NP-Hard. Now trying to prove NP completeness of some of the ...
1
vote
1answer
51 views

Need of reducing problems if we already know that a problem is undecidable

In the Reducibility chapter of Sipser's Theory of Computation book, an example is: We reduce A(TM) to HALT(TM). And then we claim that if H decides HALT(TM), then A decides A(TM), but since A(TM) is ...
1
vote
1answer
67 views

Reducibility in Computability Theory

In Sipser's book of Theory of Computation, related to Reducibility, it's written if A is undecidable and reducible to B, B is undecidable. The confusion is, only a solution to B determines a ...
-2
votes
1answer
72 views

MIS algorithm for Tree in O(log* n) time

I know Distributed Graph Coloring algorithm in O(log* n) which is given at P11: Vertex Coloring Same for Maximal Independent Set [MIS] they gave remark like algorithms exist in O(log* n) time at P70: ...
1
vote
0answers
12 views

Is it possible to do reductions with non-decision problems? [duplicate]

I've recently begun studying reductions in my algorithms class. All the reductions I've seen have been from decision problem $\to$ decision problem. Is it possible to do reductions with non-decision ...
1
vote
0answers
30 views

Prove that Acyclic Subgraph is NP-Hard by showing Independent Set can be reduced to Acyclic Subgraph

I am trying to prove that the Acyclic Subgraph Problem (AS) is NP-hard by showing that the Independent Set Problem (IS) is polynomially reducible to AS. AS is as follows: Given a directed graph G = ...
1
vote
1answer
75 views

How is it possible for a problem to be NP-Complete under polylog-time reductions?

I have no source for this, but I've heard people offhandedly mention problems that are NP Complete under polylog reductions (I think SAT was one of them). This confuses me - it seems to me that this ...
2
votes
1answer
169 views

Why is the reduction from Vertex-Cover to Subset-Sum of polynomial time?

In the standard proof why Subset-Sum is (weakly) NP-complete, one reduces Vertex Cover to Subset-Sum by using suitable numbers with O(m+n) bits (where m is the number of edges and n the number of ...
2
votes
1answer
68 views

How to reduce MAX-2SAT problem to finding a cut in a graph

I'm trying to reduce the MAX-2SAT problem to finding a cut in a graph, with no luck so far. Let me first show a description of the problem: 2SAT: Given a boolean formula $\varphi$ in a CNF form, where ...
1
vote
1answer
33 views

Reducing optimization problem to decision problem

I'm trying to reduce an optimization problem to a decision problem, more specifically, consider the Max-Cut problem in its decision version: Given $(G=(V,E),k)$ as input, where $G$ is an undirected ...
2
votes
2answers
74 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
40 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
101 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
57 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
35 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
30 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
55 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
57 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
47 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
102 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
54 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
96 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
270 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 ...