New answers tagged reductions
1
The problem is NP-complete even if the player can buy/sell a fraction number of a droid. We reduce Not-All-Equal 3SAT (NAE3SAT) to this problem.
Given an instance of NAE3SAT with $n$ variables $x_1,\ldots,x_n$ and $m$ clauses, we construct a graph like follows.
s ---> x_1^0 --> x_2^0 ... x_n^0 ---> t
\ \/ /
\ ...
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 ...
1
To prove a problem is NP-complete you have to prove it is in NP and that it is NP-hard.
NP-hardness proof is usually however, a reduction from one NP-hard problem. To prove that the problem is NP, you can either describe a non-deterministic polynomial time algorithm for the problem (An NTM that decides the language of the yes-Instances in polynomial time), ...
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 ...
1
Let $P$ be an arbitrary simple path in the graph. If $P$ appears in a Hamiltonian cycle of the graph, you can remove all the vertices of $p$ except the first and the last vertex, connect these two vertices with an edge and the resulting graph must be Hamiltonian.
Keeping this in mind, we can build the Hamiltonian cycle step by step starting with path of ...
1
If I understand correctly you only have a problem when the graph $G = (V,E)$ of the vertex-cover instance has isolated vertices. In this case you can transform $G$ into a related graph $G' = (V \cup \{x,y \}, E')$ by adding a two new vertices $x$ and $y$ such that $x$ and $y$ are connected to each other by an edge, and there is an edge between $x$ and each ...
0
All decidable problems can be reduced to the halting problem, since you can build a machine that solves the problem in bounded time and place (even if the bound was super exponential) and accepts if the output is yes else it goes into a loop.
A more interesting example is the post correspondence problem. It is a well-known undecidable problem. The proof is ...
0
Before Fermat's Last Theorem was proved, it could easily be reduced to the halting problem: You can easily write a program that will halt if and only if there are 1 ≤ a ≤ b ≤ c, and n ≥ 3, such that $a^n + b^n = c^n$. A proof that the program halts or not would have proved that FLT is wrong or right. And a solution to the halting problem (a program that can ...
0
You need two steps to show that a problem $T$ is NP-complete.
Step 1. Show that $T$ is at least as hard as an NP-complete problem
In other words, show that $T$ is NP-hard.
To do this, you choose your favorite NP-complete problem $Q$, and then show that for every instance of $Q$, you can model an instance of $T$ that corresponds to $Q$. Thus, an algorithm ...
0
To prove a problem B is NP-complete given that problem A is NP-complete (A = independent set, B = vertex cover, in your case), you start with an instance of problem A and transform it into an instance of problem B.
This reduction from A to B implies that (every instance of) problem A can be reformulated as (an instance of) problem B. In other words, ...
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 ...
0
I think there is a greedy way to solve this.
First, note that the $m$ $a_i$ values of triplets should be the $m$ largest values of $S$.
Then for the $2 m$ remaining values. Follow the decreasing $a_i$ and select the pair ($a_j$, $a_k$) among the remaining values to minimize $D = a_i-a_j-a_k$ respecting $D \ge 1$.
If you cannot there is no solution. This ...
1
You reduce Independent set to Vertex cover. You want to say that the vertex cover is atleast as hard as Independent set. One could way to remember is you are using a subroutine for vertex cover to solve Independent set. Since Independent set is Np-C you know you know the subroutine you used can't be polynomial. If you do the other way around using a ...
0
Maybe like this. We can add two connected vertex l1 and l2. First, we connect them with any vertex v*. Notice that this behavior means that at last, we just lock some color come vertexes including v*.
Then we run the decision version of the 3-colorability, if the decision algorithm accepts, then we add this vertex into s_1. we repeat this step with every ...
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 ...
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, ...
0
So I have to find a manipulation of $p$ such that I only have even numbers as solution.
Not so. You have to find a manipulation of $p$ such that if you can find a solution / all the solutions of the manipulated $p'$ in even numbers, then you can find a solution / all the solutions of $p$. That's a very different problem.
1
My paper (Reducing 3SUM to Convolution-3SUM, to be published in SOSA 2020) studied a relevant version of your problem. Basically the result we get is we can solve 3SUMx1 deterministically with the same deterministic running time as for 3SUMx3. (However this does not directly give any results in your oracle description.)
Top 50 recent answers are included
