| Speaker: | Alan Woods Department of Mathematics University of Western Australia | |
|---|---|---|
| Topic: | "Unsatisfiable Systems Of Equations, Over A Finite Field" | |
| Date: | Tuesday, November 3, 1998 | |
| Time: | 3:15 PM | |
| Place: | Mathematics, Room 501 |
Consider the question of whether a system of simultaneous quadratic equations in n variables, has a solution in the q element field GF(q). Even for q = 2 this problem is known to be NP-complete. If the system is satisfiable, there is a short proof of this fact, namely exhibit a solution. In general it seems to be much more difficult to prove that a given system does not have a solution. The obvious brute force search involves looking at all potential solutions, of which there are q to the power n.
However considering systems unsatisfiable in some set S, leads to an interesting (although in general computationally demanding) formula for the number of solutions of any system, satisfiable or not.
Making use of this formula, it turns out that for any system unsatisfiable in GF(q), there is a proof of unsatisfiability, whose size, and machine checking time, are only about the square root of the number of steps required for an exhaustive search of all potential solutions. With some probabilistic preprocessing, a proof of this sort can even be constructed algorithmically in the course of such an exhaustive search.