Hilbert’s Nullstellensatz and certificates for co-NP

[Stas Busygin]

Terence Tao presents in his blog Hilbert’s Nullstellensatz in terms of
obstruction to satisfiability of a system of polynomial equations:

"Weak nullstellensatz. Let P_1,\ldots,P_m \in F[x] be polynomials.
Then exactly one of the following statements holds:
1. The system of equations P_1(x)=\ldots=P_m(x)=0 has a
solution x \in F^d.
2. There exist polynomials Q_1,\ldots,Q_m \in F[x] such that
P_1 Q_1 + \ldots + P_m Q_m = 1."

http://terrytao.wordpress.com/2007/11/26/hilberts-nullstellensatz/

So, if those Q's were polynomial in size, we would have solving a
system of polynomial equation to be in co-NP, and then NP=co-NP as
there are NP-complete problems which can be easily formulated as a
system of polynomial equations.

So I wonder if there are simple examples where Q's must be exponential
in size? In particular, if I formulate clique>=K decision problem as

\sum_{i \in V} x_i = K,
x_i x_j = 0 \forall (i,j) \notin E, i \neq j,
x_i - x_i^2 = 0 \forall i \in V,

what is an example of a class of graphs that require exponential Q's?


--Stas

[Stas Busygin]

On May 1, 12:27 pm, Stas Busygin <busy...@gmail.com> wrote:
>
> So I wonder if there are simple examples where Q's must be exponential
> in size? In particular, if I formulate clique>=K decision problem as
>
> \sum_{i \in V} x_i = K,
> x_i x_j = 0 \forall (i,j) \notin E, i \neq j,
> x_i - x_i^2 = 0 \forall i \in V,
>
> what is an example of a class of graphs that require exponential Q's?

Checked some small graphs with SINGULAR. It looks like Q_0
(corresponding to \sum_{i \in V} x_i = K) contains all terms
corresponding to maximal cliques, so the exponentiality is trivial.