3
$\begingroup$

This is a follow-up to the previous question on the same topic. Thanks to Emil Jeřábek I can now ask a more specific question.

As before, let $k$ be a field with $p$ elements. Consider the following computational problem.

Input: a natural number $n$, $n^2$ linear forms $M_{ij}$, $i,j=1,\ldots n$ in $n^2$ variables $X_{11}, \ldots X_{nn}$.

Problem: Is there an assignment of values to the variables $X_{ij}$ so that the matrix $M_{ij}$ is invertible?

As usually, let's assume the addition and multiplication in the field to have computational cost $1$.

On the one hand, we have a trivial algorithm of checking all the possible assignments for $X_{ij}$, and for each such assignment checking by Gauss elimination whether the resulting matrix is invertible. This takes time bounded by a polynomial in $p^{n^2}$.

On the other hand, Emil Jeřábek showed previously that we can encode a 3-SAT instance consisting of $n$ clauses into a $3n\times 3n$ matrix of linear forms which is invertibe iff the 3-SAT instance is satisfiable. Assuming exponential time hypothesis this gives a lower bound on the problem above of the form $O(2^{\delta n})$ for some $\delta>0$.

Question 1 Is there an algorithm for the problem above, whose execution time is bounded by a polynomial in $p^{n^\alpha}$ for $\alpha <2$?

Question 2 Is there a natural number $k$ such that one can encode a 3-SAT instance with $n^\beta$ clauses into a problem as above for a $kn\times kn$ matrix, for $\beta>1$?

$\endgroup$
  • $\begingroup$ Probabilistic checking of invertibility means choosing values at random and evaluating the resulting determinant and seeing if it is nonzero. This is O(n^3), with a good chance of success if there are such values. Is the 3SAT problem solved if we find such values? Gerhard "Ask Me About System Design" Paseman, 2011.12.07 $\endgroup$ – Gerhard Paseman Dec 7 '11 at 18:36
  • $\begingroup$ @Gerhard: As discussed in the previous question, this probabilistic algorithm only works if the size of the field is larger than the degree of the polynomial (i.e., $n$). Here, the field size is constant. $\endgroup$ – Emil Jeřábek Dec 7 '11 at 18:39

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Browse other questions tagged or ask your own question.