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.