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 ...
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 ...
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
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 ...
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 ...
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 ...
1
If $G=(V, E)$ is the graph of an instance of CLIQUE-or-almost to CLIQUE,
then you can create a new graph $G'$ as the disjoint union of $G$ with all the graphs $G + e$ for $e \in \binom{V}{2} \setminus E$.
Then $G$ has a clique or an almost-clique on $k$ vertices if and only if $G'$ has a clique on $k$ vertices.
This shows that CLIQUE-or-almost $\le_p$ ...
1
Here is a reduction from CLIQUE to CLIQUE-or-almost.
Let $G$ be an arbitrary graph. Form a new graph $G'$ by adding two new vertices $x,y$ connected to all vertices of $G$, but not to each other. If $G$ contains a $k$-clique, then $G'$ contains a $(k+2)$-clique with a missing edge.
Conversely, suppose that $G'$ contains a $(k+2)$-clique $S$, possibly with ...
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.)
Only top voted, non community-wiki answers of a minimum length are eligible
