FOM: Small but critical correction to previous post. JoeShipman at
Tue Aug 25 04:25:07 EDT 1998

Oops!  I meant to refer to the "circuit value" problem, not the
"satisfiability" problem--the circuit value problem is PTIME-complete but
appears unlikely to be in DSPACE(log(n)^2).  My apologies for not proofreading
my post before sending it! - JS

More information about the FOM mailing list