
PreviousNext
Linear threshold elements are the basic building blocks of artificial neural
networks. A linear threshold element computes a function that is a sign of a
weighted sum of the input variables. The weights are arbitrary integers;
actually, they can be very big integers---exponential in the number of the
input variables. ...
more >>>
The paper analyzes in terms of polynomial time many-one reductions
the computational complexity of several natural equivalence
relations on Boolean functions which derive from replacing
variables by expressions. Most of these computational problems
turn out to be between co-NP and Sigma^p_2.
We investigate the computational complexity of the Boolean Isomorphism problem (BI):
on input of two Boolean formulas F and G decide whether there exists a permutation of
the variables of G such that F and G become equivalent.
Our main result is a one-round interactive proof ... more >>>
PreviousNext