Path: utzoo!attcan!uunet!cs.utexas.edu!know!zaphod.mps.ohio-state.edu!swrinde!emory!hubcap!sarnath
From: sarnath@sybil.cs.buffalo.edu (Ramnath Sarnath)
Newsgroups: comp.parallel
Subject: Circuit value problem
Message-ID: <9546@hubcap.clemson.edu>
Date: 3 Jul 90 13:08:35 GMT
Sender: fpst@hubcap.clemson.edu
Lines: 12
Approved: parallel@hubcap.clemson.edu

I would like to know the status of the following problem : 
(i.e, does it belong to logspace/NC, is it logspace complete for P, etc)

	Given a boolean circuit made up entirely of xor gates together
with a set of inputs, is the output of every node of the circuit true?

(the problem of actually obtaining the outputs, is logspace complete
for P).

If there is some known result, I would appreciate references.

sarnath@sybil.cs.buffalo.edu