[comp.theory] question on boolean circuit evaluation

ponder@lll-crg.llnl.gov (Carl Ponder) (04/04/91)

	Here are 3 problems in evaluating boolean circuits that I am
interested in. I expect they have been looked at, if not solved already,
and I would appreciate it if anyone could point me to the relevant 
papers etc:

	1] evaluation of boolean circuits: given a circuit and the settings
	    of its inputs, how quickly can you figure out its output(s)? 
	    It seems like there ought to be methods which, on the average,
	    take time sublinear in the number of circuit components.

	2] offline transactions: given a circuit, the initial settings of
	    its inputs, a sequence of changes to the inputs and the times
	    they occur, and a sequence of times t_i, how quickly can you
	    figure out the output(s) at each of the times t_i?

	3] online transactions: as with [2], except produce the output
	    sequence online as the new settings and query times are read
	    in. It would also be useful to allow an arbitrary amount of
	    pre-processing on the circuit and its initial settings.


I am primarily interested in serial algorithms with good worst-case or
expected-case complexity, and lowerbound arguments. The construction
and analysis of parallel or nondeterministic algorithms might shed some
light. Any leads would be appreciated. Thanks,

	   					  Carl Ponder
	   					  ponder@lll-crg.llnl.gov