next up previous
Next: Signature of Up: Open problems with signatures Previous: Open problems with signatures

Signatures of boolean expressions

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