12
The premise of the question is a little flawed: there are many who would argue that quadratics are the real "boundary" for tractability and modelling, since least-squares problems are almost as 'easy' as linear problems. There are others who'd argue that convexity (or even submodularity in certain cases) is the boundary for tractability.
Perhaps what is ...
11
I’m not sure this is a research-level question, however solving linear systems over $\mathbb F_p$ is a $\mathrm{Mod}_p\mathrm L$-complete problem, hence in particular it is in $\mathrm{NC}^2$. More generally, linear algebra over $\mathbb F_{p^k}$ (at least for $k$ fixed) can be reduced to the $\mathbb F_p$ case.
9
If by "classically using the solutions of the linear equation" you mean "accessing the information in the exactly same way a classical computer does" or, in other words, "obtaining the classical solution $x$ to a system $Ax=b$" then the answer is no. As you mention, the final quantum state in Harrow, Hassidim, Lloyd's algorithm does not immediately give you ...
6
Yes, if the encryption algorithm achieves IND-CPA security (semantic security), this implies that an adversary cannot predict any linear combination of encrypted bits better than random guessing.
The easiest way to see this is to note that IND-CPA (left-or-right indistinguishability) implies real-or-random indistinguishability under chosen-plaintext attack:...
6
A result known for over 30 years is that Guassian Elimination over $\mathbb F_2$ can be done by a various decompositions which takes $O(n^\omega)$, where $\omega$ is the matrix multiplication constant.
References:
Ibarra, O. , Moran, S. , and Hui, R. 1982. A generalization of the fast LUP matrix decomposition algorithm and applications. Journal of ...
6
Yes, it is well known it can be done by diagonalizing the matrix using row and column operations. An outline of the procedure is given in the paper The Complexity of Solving Equations over Finite Groups by Goldmann and Russell.
answered May 28 '13 at 9:06
Kristoffer Arnsfelt Hansen
3,9152 gold badges23 silver badges34 bronze badges
5
"Although we have non-linear systems prevalent all around us how/why are linear systems so crucial to computer science?"
Here is a partial answer in my mind:
I think it is because nature is abound with objects/phenomena - representable by functions which albeit being nonlinear on their operands, are actually members of linear spaces. The wave functions in a ...
4
In the general case, your problem is NP-hard, if you are working over a finite field (say, the integers modulo $p$). It is easy to see that the language of such circuits that are not identically zero is in NP (if it isn't identically zero, there exists a witness: an input that makes its output non-zero).
Also, we can reduce SAT to this problem. Consider a ...
2
Jacobi or Gauss-Seidel are not really state of the art for solving systems of linear equations. It is more done by preconditioned conjugated gradient (for symmetric positive semi-definite matrices) and preconditioned (F)GMRES (or other Krylov subspace methods) for arbitrary matrices.
The crucial part here is the preconditioner. There was recently (=21th ...
Only top voted, non community-wiki answers of a minimum length are eligible
