Tag Info

5

One possibility is to take the tensor squares of the vector: replace each vector $x$ with a new vector $\hat{x}$ given by $\hat{x}_{ij} = x_i x_j$ (the vectors have length $k^2)$. We have $$\langle \hat{x}, \hat{y} \rangle = \sum_{ij} x_i x_j y_i y_j = \langle x,y \rangle^2.$$ Therefore if you know the minimum inner product, you can solve OV. It remains to ...

2

Miltersen, Radhakrishnan and Wegener construct, in their paper On converting CNF to DNF, a function which has a polynomial size CNF, but whose smallest DNF has size $2^{n-\Theta(n/\log n)}$. In particular, even if the input CNF has polynomial size, you cannot expect to do better than exponential time, since the output might be that long.

2

Can't make a comment so have to use an answer. It's a well-known fact that every non-trivial language in $L$ is complete under log-space reduction because the reduction could be used to decide the language with only two values for a mapping.

2

To prove the reverse direction you need to show that if there exist a subsequence $S_1$ in $(a_1+K,a_2+K,\dotsc,a_n+K,K,\dotsc,K)$ that sums to $T+nK$, then there is a subsequence $S_2$ in $(a_1,\dotsc,a_n)$ that sums to $T$. The proof would become easy if we assume that $S_1$ only contains $n$ elements. If that happens, then the above statement holds. (hope ...

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