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

learn more… | top users | synonyms

0
votes
1answer
11 views

Reduce Clique to Vertex Cover

I read on the internet that it's possible to reduce Clique to Vertex Cover. Almost everyone use this theorem: if a graph $G$ has a clique of size $k$ then the complement of $G$ has a vertex cover of ...
-1
votes
1answer
17 views

SAT-3CNF - Clique

Could someone show me ( or give me a valuable hint) how to reduce k-Clique problem to SAT-3CNF problem ? I am able to prove reduction from SAT-3CNF to k-Clique, but in the opposite direction it's ...
1
vote
0answers
21 views

reduction of maxcut problem

Show that if the MAX CUT decision problem can be solved in polynomial time so can the MAX CUT optimization problem by writing an algorithm that solves the optimization problem using an algorithm for ...
2
votes
1answer
51 views

Reduction from a further constrained problem

If I find an NP Hard problem that is equivalent to my problem with an additional constraint or bound, can I still prove that my problem is NP Hard? Generally, this is probably not the case. For ...
2
votes
1answer
208 views

Reducing a non-RE language to its complement

Is there a language $L$ such that both $L$ and $L$'s complement are non turing recognizable languages, but there is a reduction between them? I couldn't find one...
0
votes
1answer
24 views

Reductions where the number of certificates from one problem can be computed for another to varying degrees

Let $A$ and $B$ be two decision problems in $NP$. Consider three cases: (1) For any instance of problem $A$, one can produce, in polynomial time, an instance of problem $B$ having exactly the same ...
0
votes
1answer
27 views

Validity of reduction (3-SAT)

I'm trying to show that a special variant of the common 3-SAT is NP-complete by reducing 3-SAT to this special variant. This special variant works like the normal 3CNF-SAT, except every other clause ...
1
vote
1answer
29 views

Randomized and deterministic reduction

Given a problem $X$, to show it is is $\sf NP$-complete, one usually shows a deterministic reduction from an $\sf NP$-complete problem. If it is hard to show deterministic reduction, then one shows a ...
3
votes
1answer
46 views

Characterizing the range of a polytime function

Is it true that an infinite language is in P iff it is the range of a length increasing polytime function? I ask because I know that it is a basic result in computability theory that a set is ...
3
votes
2answers
48 views

Can someone provide a trivial example to the “reduction” procedure used to prove hardness? [duplicate]

I cannot comprehend how you can prove hardness between two NP complete problems. For example, let X be a NP hard problem, I want to prove Y is also NP hard. I can do this by reducing X to Y, if Y is ...
1
vote
2answers
53 views

Turing Machine That Accepts Machines With Undecidable Languages

So I'm reviewing my Computability notes for my final, and I understand how reduction arguments work, but I'm having trouble framing one for the following Turing machine: Undecidable TM = { ⟨M⟩ | L(M) ...
3
votes
3answers
299 views

Understanding reductions: Would a polynomial time algorithm for one NP-complete problem mean a polynomial time algorithm for all NP-complete problems?

To prove that some decision problem $A$ is NP-complete, my understanding is that it suffices to show that the problem is in NP (i.e. that one can verify or reject all statements in polynomial time), ...
1
vote
1answer
35 views

Proving a function is uncomputable [duplicate]

I am trying to solve the following problem: For each Turing machine $M_k$ and each string $x$ in $\{$0,1$\}$$^\ast$ let $time_k(x)$ = $\{$the number of steps executed by $M_k(x)$ if ...
5
votes
1answer
210 views

How a reduction can help up solve a problem?

I am studying the basics of Computation Theory and I came up with an example I can't understand. Let's have a language $L = \{\langle M\rangle \mid L(M) = \Sigma^{\ast} \}$, so $L$ contains codes of ...
2
votes
0answers
25 views

How to convert a rank constraint into integer programming?

Consider the low-rank matrix completion problem: given an integer $k$ and a subset of entries of some matrix, can you fill in the rest of the entries so that the resulting matrix has rank at most $k$? ...
-3
votes
1answer
91 views

Showing that M is NP-Complete

An instance of $M$ is a collection of sets $S_1, \dots, S_m$ and a bound $B$. A solution is a set $T$ containing $B$ distinct items, such that each item in $T$ belongs to some $S_i$, and ...
0
votes
0answers
27 views

Is it decidable whether a TM accepts more than one word?

Is the following language: $\qquad\displaystyle L= \{\langle M\rangle \mid M \text{ is a TM }, |L(M)|>1\}$ Turing-decidable? I think it isn't, because if a Turing machine T can ...
0
votes
0answers
35 views

Reduction of specific scheduling problem to show np-completeness

Given a Set K of n tasks, a set T of t possible time-intervalls to schedule any task, and a number k: Is there a schedule for the tasks, such that there are at most k conflicts (time - overlaps) of ...
1
vote
3answers
58 views

If A is in P and B is non-trivial, then A ≤p B [duplicate]

On wikipedia's article on Polynomial-time reduction it states: Every nontrivial decision problem in P (the class of polynomial-time decision problems, where nontrivial means that not every input ...
1
vote
1answer
137 views

Reducing context-free languages with polynomial-time reductions

So, let's say we have two languages $L$ (which is any context-free language) and $M$ which is the basic CFL $\{0^n1^n: n\geq 0\}$. Can $L \le_p M$ ? Why or why not? How do polynomial time reductions ...
4
votes
1answer
30 views

3 dimensionnal matching to partition transformation

We want to transform $3DM$ to $PARTITION$, I am reading Garey and Johnson book and I really don't understand how they do the transformation, I know how they create elements $a_i$ from triples of set ...
0
votes
1answer
35 views

All but Five Three Colorable

An NP Problem Named All But Five Three Colorable(AB53C) is defined as follows :- Input : Connected Graph G(V,E) The Connected Graph is AB53C, iff the Given Graph is 3-Colorable by leaving UPTO 5 ...
2
votes
1answer
48 views

NP completeness of closest vector problem

Let $\mathcal{B} = \{v_1,v_2,\ldots,v_k\} \in \mathbb{R}^n$ be linearly independent vectors. Recall that the integer lattice of $\mathcal{B}$ is the set $L(\mathcal{B})$ of all linear combinations ...
3
votes
1answer
31 views

Can someone explain in a simple way what “reducible” mean in complexity theory? [duplicate]

I find the word "reducible" used in complexity theory not very intuitive, and too general taken on a face value. What does it exactly mean by problem A reducible to B? Does it mean that A can be ...
0
votes
0answers
33 views

Request for help with two reductions

Given two graphs one needs to decide if one of them has a subgraph isomorphic to the other. Given a subset of a graph one needs to decide if the induced subgraph is triangle free. Can someone ...
-1
votes
1answer
43 views

Prove NP Complete

There are n numbers and we have to split the numbers into 2 sets such that difference of the sum of numbers of both sets is less than 100. Is this problem NP complete? Solution: I can prove that it ...
1
vote
1answer
61 views

Formulate the Marriage Problem into a Maximum-flow problem (Graph theory)

Suppose I have $M=\{1,\ldots, n\}$ men and $W = \{1, \ldots, n\}$ women and $B =\{1, \ldots, m\}$ brokers, such that each broker knows a subset of $M \times W$ and for each pair in this subset a ...
0
votes
1answer
19 views

Example of reduction such that it is not many-one reduction while it is not turing reduction

I am reviewing things I learned, and I can't suddenly come up with an example of reduction that is not many-one, but Turing reduction. Can anyone present such an example?
0
votes
3answers
69 views

Show that finding a minimum-weight subgraph that includes all marked nodes is NP-hard

We've been given a weighted graph with marked nodes. We want to make a minimum-weight subtree from this graph that contains all marked nodes. I want to show that this problem is NP-hard. Is there any ...
5
votes
0answers
59 views

NP-hardness of a special traveling salesman problem

Consider we have $n$ vertices, $v_1,\ldots,v_n$. We have two positive values $(a_i,b_i)$ associated with each $v_i$. The edge weight $w(v_iv_j)=a_ia_j+b_ib_j$. Is it NP-hard to solve the traveling ...
1
vote
1answer
87 views

Karp reduction from 3-SAT to 3-PARTITION

I want to show that this problem is NP-complete: partition a set of 3n real numbers to n partitions of 3 number which each partition has the same sum of its members. I want to reduce 3-SAT to this ...
-1
votes
1answer
26 views

polynomial time reduction of 2 langauges

If we can reduce a language y to x. x ≤P y how do I prove x(complement) ≤P y (complement)
2
votes
1answer
34 views

Polynomial Time Reduction - Does 0 calls to the black box still imply a reduction?

Using the following definition: Reduction: There is a polynomial-time reduction from problem $X$ to problem $Y$ if arbitrary instances of problem $X$ can be solved using: Polynomial ...
4
votes
1answer
29 views

Is complexity of $GI_{di}$ same as $GI_{un}$?

Does the graph isomorphism problem for directed graphs($GI_{di}$) reduce to the graph isomorphism problem for directed graphs($GI_{un}$)? It is clear $$GI_{un}\leq GI_{di}$$ since the set of ...
0
votes
1answer
73 views

Is the identity function a many-one reduction from a language to super-set?

I need help with a question. Prove or disprove the following claim: Let $f\colon \Sigma^* \to \Sigma^*$ be the identity function, i.e., $f(w) = w$ for all $w \in \Sigma^*$. Let $L_1$ and $L_2$ be ...
3
votes
1answer
187 views

Could two decidable languages ever not have a mapping reduction?

Is it ever the case that two decidable languages $L_1$ and $L_2$ that cannot be reduced to one another (in either or both directions)? Intuitively, I would not expect there to be, but rigorously, are ...
1
vote
1answer
47 views

Is the maximum coverage variant of Vertex Cover also NP-hard?

In Chapter 3 of "Approximation Algorithms for NP Hard Problems" edited by Prof. Dorit S. Hochbaum, there is such a sentence that "Maximum Coverage Problem is clearly NP-hard, as Set Cover is reducible ...
4
votes
3answers
59 views

When problem A reduces to problem B, which problem is more complex?

When discussing complexity classes, when we say that problem $A$ reduces to problem $B$, are we saying that problem $A$ is at least as complex as problem $B$, or the other way around?
1
vote
1answer
20 views

Hardness and approximation of a problem with a parameter

Let $H$ be a decision problem, where we are given an integer $k$ and some object, say a graph or a formula. We know that $H$ is NP-complete for $k \geq c$, where $c$ is some constant like 3 ($H$ could ...
1
vote
1answer
33 views

Is $K' = \{ w \in \{0,1\}^* | M_w$ Halts on $w \}$, where $M_w$ is the TM whose encoding is $w$, equivalent to the halting problem?

My professor presented the halting problem as $K' = \{ w \in \{0, 1\}^* | M_w$ Halts on $w \}$, where $M_w$ is the TM whose encoding is $w$ (i.e. $w = \langle M \rangle$), and said it was equivalent ...
-1
votes
1answer
57 views

Proof that L(M) = {accepts the string 1100 } is undecidable

Let $$L_\ = \{\langle M\rangle \mid M \text{ is a Turing Machine that accepts the string 1100}\}\, .$$ To proof that the language $L$ is undecidable I should reduce something to $L$, right? I tried ...
0
votes
2answers
64 views

NP-hard proof with reduction from two known NP-hard problems

As I understand, to show that a certain problem P is NP-hard we can reduce a known NP-hard problem, Q, to problem in P in polynomial time. To show that the problem P is NP-hard in strong sense, we can ...
2
votes
1answer
37 views

Proof of P-Hardness by reduction

I want to proof the P-Hardness of a language. Why is it enough to make a reduction-proof from an other, already P-Complete known language?
0
votes
0answers
14 views

When proving a problem is NP-C, how do I select another NP-C problem for the transformation? [duplicate]

I'm taking an algorithms course in which we are discussing proofs that problems are NP-Complete. Our proofs usually take the form: Given a problem $\Pi$, 1. Prove that $\Pi$ is NP. 2. Select an ...
6
votes
0answers
54 views

Is There a Complete Problem for the Class of Turing Decidable Problems?

Languages such as $\text{HALT}_{TM}$ are $\textsf{RE-complete}$ under many-one reductions. It is trivial to see that $\text{co-RE}$ has complete problems, too. S. Schmitz [1] considers some classes ...
-1
votes
1answer
169 views

How to reduce bin-packing problems? [duplicate]

This is my first time with reductions and I can't figure out how to do them. I have read the few standard examples that are given in the standard books. For example, given $n$ numbers $\{ 0 < ...
4
votes
1answer
38 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, ...
2
votes
1answer
105 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
53 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 ...
5
votes
2answers
80 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 ...