Linear separability

[Simon Kasif <kasif%crabcake@crabcake.cs.jhu.edu>]

>
>
An interesting offshoot of this question is whether it is possible
to determine linear separability of an ENTIRE (on the whole cube) boolean
function, when the input is a description of a CIRCUIT computing the
function. The circuit description is obviously polynomial, otherwise
the function is definitely NOT linearly separable (all linear
threshold functions are in NC1).

I'd be interested in knowing if anyone can answer this.

>
>
If I understood your question correctly, 
this seems to depend on the representation of the boolean
(function) circuit. If the function F is given as a formula in CNF,
then the question become co-NP.
Simply observe that the formula F*G (F and G), where G represents
some easy non-linearly separable function (e.g. XOR) over the
same input, is a linear threshold function (all inputs map to 0) 
iff F is unsatisfiable.