Below is Mathematica printout showing the usefulness of tautologies.

tautologies6vars4thOrder

Given and equations , one can expact 64 dimensional nullspace in the space of monomials of some degree. The above show that in the usual * Nullstellensatz * case one need 8th order monomials, whereas it is sufficient to have tautologies variables of equivalent degree 6. This is on decoding side.

The encoding (problem equations) side still need some work to be done. What is obvious is that there is much more than just multiplication by a monomials. For example, take quadratic encoding polynomial . In tautology variables it is linear equation, but than one can split it into two halves on the right and left side and square it. One can also take cubes, that is still possible since we are looking at equivalent 6th order polynomials. One has exponentially many ways to split encoding equation. The question here how to extract relevant information in, say, polynomial time.

### Like this:

Like Loading...

*Related*