# Tag Info

## Hot answers tagged reductions

6

No. A state of $n$ qubits can be represented with a vector of size $2^n$, and quantum gates can be implemented as linear operations for those vectors. Therefore a quantum computer can be simulated with a Turing machine, although with an exponential overhead. It is also known that the class of problems solvable by a quantum computer in polynomial time, BQP, ...

5

There is no known natural example of such a pair, and indeed there are various results in computability theory suggesting that such a pair does not exist. So to whip up an example one has to do some work. The simplest approach (indeed, the easiest I know) is via mutual diagonalization: we build inductively a pair of increasing sequences of infinite binary ...

5

The reduction is possible. I'll give a reduction of minimum feedback arc set to minimum feedback arc set with maximum outdegree two. The basic idea is that if node $i$ has outdegree $d_{i}$, we make $d_{i}$ copies of node $i$. We add new nodes representing edges so that edges can still be cut in one operation. Say the graph we want to solve minimum ...

5

No, this problem is in $\mathbf{P}$. The main point being that the sum of all the values is $1 + 2 \ldots + n = \frac{n(n+1)}{2} = \mathcal{O}(n^2)$, which is polynomial in the input size. Without the extra restriction of $v_i = i$, the sum of all the values could be exponential in the input size, as the values are represented in binary in the input. So we ...

5

You are correct. 3-clique can be solved in $O(n^3)$ time, whereas 3-coloring is NP-hard. So there can be no "poly-time reduction" from 3-coloring to 3-clique, unless $P=NP$.

4

The only two methods I've seen are (a) a reduction or (b) direct proof (as in the proof of the Cook-Levin theorem). It is almost universally the case that a reduction is easier than a direct proof. Therefore, I suggest you keep trying to find a reduction, and consider other reduction partners. There are lots and lots of problems known to be NP-complete; ...

4

In Computational Intractability, we often come across a need to reduce Vertex Cover (VC) problem to a Subset Sum problem... We do? ... mostly to prove Subset Sum is NP-Complete. There's no particular reason to go down that route. Karp [1] defined the Knapsack problem as: given $a_1, \dots, a_r, b\in\mathbb{Z}$, is there a set $S\subseteq \{1, \dots,... 4 This is known as the distance-$d$independent set, i.e., you are looking for an independent set of size$k$where the distance between every two elements in the solution is at least$d$. The problem is NP-complete even on planar graphs according to [1], but I don't know about its complexity on partial grids. Regarding reductions, you can probably take the ... 4 You can always satisfy at least half of clauses: for each variable$x$, find the number of clauses that contain$x$and the number of clauses that contain$\lnot x$. Select the one which satisfies the most clauses. Remove clauses containing$x$and$\lnot x$. Repeat for other variables. Since for each$x$we satisfy at least half of removed clauses, we ... 3 Oddly enough, I could not find any example of NP-hardness reduction done directly by modeling the problem as a language, and showing that a deterministic Turing Machine cannot decide whether a given instance belongs to that language (I might've messed up with the terminology here) That's not odd at all: it's because no such proof exists. Anything that can ... 3 I know an example of a problem that is missing two of the four features you ask for - it is not NP-complete, and it is not a problem on graphs. Buchfuhrer and Umans (2011) show that the minimum equivalent expression problem in Boolean logic is complete for$\Sigma^P_2$under polynomial-time Turing reductions. Given a Boolean$(\wedge;\vee;\neg)$-formula$F$... 3 Let$S, k$be a given instance of the subset sums problem. The goal is to build an equivalent instance of your problem (let us call it the pens arrangement problem). In the subsetsums problem, we are looking for a subset of the given set that sums up to$k$. So it is intuitive to set$G$to$k$and set the lengths of the pens to be the numbers in the given ... 3 You can find a simple reduction from Knapsack or from the Partition Problem (which itself reduces to Knapsack). Let's do it from the Partition Problem: Given$n$integers$S = \{a_1, a_2\ldots, a_n\}$with even total sum, does there exist a subset whose sum is exactly half the sum of all elements ? So suppose you are given an instance of the Partition ... 3 Using the proof of the Cook–Levin theorem, for every input$x$you can construct in polynomial time a SAT instance$\phi(r,z)$which encodes "$M$accepts when run on input$x$and randomness$r$". Here$r$is a vector of$m = \mathit{poly}(n)$bits, representing the random bits of$M$, and$z$is an auxiliary vector, with the following property: in any ... 3 Computer Science is far too diverse to have a single notion of program. For a theoretician, it might be an input tape to a universal Turing Machine, or any lambda expression in lambda calculus. For someone working on the front end of a compiler, it could be defined by a formal grammar while for someone working on the back end, or to the HW architect, it ... 3 The problem is NP-hard, at least for a particular simplified configuration. Assume that each$m_l$is effectively infinite - we can scan a particular libraries' books all on the day we get access. Let all$d_l = 1$- each library takes one day to get access to, meaning we get access to exactly$n$libraries. Now if$P_b = 1$the thing that maximizes our ... 3 Let special vertex cover be the special case of vertex cover in which$|V| = 2k+1$. We later reduce vertex cover to special vertex cover. Now suppose we're given an instance$G = (V,E),k$of special vertex cover. Construct an instance$G',k$of half vertex cover by attaching$|E|$new edges to each vertex in$V$. The total number of edges in the new graph ... 3 Let me explain how to solve this, leaving all details to you. Given an instance$(G,k)$of CLIQUE, we want to construct an equivalent instance of$\frac{n}{3}$-CLIQUE, say$G'$. Let us denote by$|G|$the number of vertices in$G$. There are several cases to consider: Case 1:$k = |G|/3$. In this case you can take$G' = G$. Case 2:$k > |G|/3$. In this ... 3 The number of k-tuples of vertices in a graph with$n$vertices are:$^nC_k$. You can iterate through each possible k-tuple and check in$O(k^2)$time whether the given k-tuple forms a clique. For any fixed natural$k$, the number$^nC_k$is$O(n^k)$, and hence you can check whether a graph has$k$-clique in$O(k^{2}.{^n}C_k)$; the problem would be in$P$. ... 3 Let$H$be the language of all Turing machines that halt on empty input. Clearly$H$is undecidable. Let$L = \{ (1,T) : T \in H \} \cup \{ (0,T) : T \not\in H \}$. Clearly$L$is undecidable. If$L$were decidable, then a Turing machine$M$for$L$would also imply the existence of a Turing machine$M'$that decides$H$.$M'$with input$T$simply ... 3 An NP-complete problem is in NP, by definition. No reduction needed. 2 We will reduce Vertex Cover to Edge Dominating Set and complete the proof. Given an instance of the decision version of vertex cover problem$I(G,k)$, we construct$G'$by adding$nk+k$new edges to$G$, where$n$is the number of vertices in$G$: add$k$new vertices; add an edge between each of these new vertices and each vertex in$G$, totally$nk$... 2 To show that Vertex Cover and 3SAT is "equivalent", you have to show that there is a 3SAT satisfaction if and only if there is a k vertex cover in the graph constructed in the reduction step. Assuming you are familiar with how the reduction is done, (if not ,refer to the document). Since you only asked about how this setup proves that if there exists a k-... 2 By hypothesis$Q \le_p L$, i.e., there exists a poly-time computable function$f(x)$such that$x \in L \iff f(x) \in Q$. Then: $$x \in \overline{L} \iff x \not\in L \iff f(x) \not\in Q \iff f(x) \in \overline{Q}.$$ Therefore$\overline{L} \le_p \overline{Q}$. 2 Yes. See the notion of an approximation-preserving reduction. 2 You can reduce Numeric 3D Matching (N3DM) to your problem. Given an instance of N3DM$X\times Y\times Z$with the bound$b$, say$X=\{x_1,\ldots,x_m\},Y=\{y_1,\ldots,y_m\},Z=\{z_1,\ldots,z_m\}$, construct$2m$elements$x_1+2M,\ldots,x_m+2M,M-y_1,\ldots,M-y_m$and$m$values$b-z_1+M,\ldots,b-z_m+M$for your problem, where$M$is a very large number. Now ... 2 Trivially every computable problem is reducible to$A_{TM}$. On the other extreme, there are plenty of problems which are$A_{TM}$"in disguise," which is to say that they are Turing-equivalent to$A_{TM}$- for example, it's a standard exercise to show that $$\{\langle M\rangle: M\mbox{ halts on input 0}\}$$ is Turing-equivalent to$A_{TM}$. A more ... 2 The mapping does not have to be surjective (onto) nor injective (one-to-one). In fact, any problem that can be solved in polynomial time can be polynomial time many-one reduced to any problem that has at least one accepting instance and at least one rejecting instance: just solve the original problem in polynomial time, then return the accepting instance if ... 2 In the context of reducing one language to another, I have only ever seen this referred to using phrases such as "the problem being reduced to", "the target of the reduction", etc. I don't think there is a single word for it—certainly not one that would be universally understood. 2 As in the comment, consider the collection of problems$N$-SAT (Is$\phi$, a logical formula in$N$-CNF, satisfiable?). Or$N$-coloring of graphs, for$N \ge 3$(Can the graph be colored with$N$colors?). Many NP-complete problems have some parameter (Is there a clique of size$k$in the graph? Has the digraph a feedback vertex set of size$k\$?).

Only top voted, non community-wiki answers of a minimum length are eligible