** Next:** Signature of
** Up:** Open problems with signatures
** Previous:** Open problems with signatures

The signature of a boolean expression, that is an expression
using unknowns and the operators `and`, `or` and
`not` may be easily computed mod 2.
Unfortunately we do not know how to compute these signatures
for general *n*.
Computing mod 2 is equivalent to assigning random values to
the variables and testing.
Such test may have an exponentially close to 1 probability
of failure, and hence useless.
These tests can be applied in parallel, for example using
bitwise boolean operations, on words of 32 or 64 bits.
This is just equivalent doing so many tests sequentially.
Finding a good signature, i.e. one with a probability of
failure less than 1/2, would imply that equivalence of
boolean expressions is in RPT (random polynomial time algorithm)
and hence P=NP.

*Gaston Gonnet*

*1999-07-04*