clarke@utcsri.UUCP (05/08/87)
(GB = Galbraith Building, 35 St. George Street)
SUMMARY:
THEORY SEMINAR, Thursday, May 14, 3 pm, GB120 -- Mihaly Gereb:
"How To Vote Fairly"
A.I. SEMINAR, Friday, May 15, 11 am, GB120 -- Gord McCalla:
"The SCENT Programming Advisor: Basic Architecture and Current Directions"
THEORY SEMINAR, Thursday, May 21, 3 pm, GB120 -- Sam Buss:
"The Boolean Formula Value Problem is in Alternating Log Time"
---------------
THEORY SEMINAR, Thursday, May 14, 3 pm, GB120
Dr. Mihaly Gereb
Harvard University
``How To Vote Fairly"
A.I. SEMINAR, Friday, May 15, 11 am, GB 120
Professor Gord McCalla
University of Saskatchewan
``The SCENT Programming Advisor:
Basic Architecture and Current Directions"
THEORY SEMINAR, Thursday, May 21, 3 pm, GB120
Professor Sam Buss
University of California
``The Boolean Formula Value Problem
is in Alternating Log Time"
The Boolean formula value problem is to determine the truth value of a
variable-free Boolean formula, or equivalently, to recognize the true
Boolean sentences. This talk will show that the Boolean formula value
problem is in alternating log time. Indeed, the Boolean formula value
problem is in some sense the canonical ALOGTIME-complete problem; this is
analogous to the well-known fact that the circuit value problem is the
canonical P-complete problem. These results are optimal since, for an
appropriately defined notion of log time reductions, the Boolean formula
value problem is complete for alternating log time under deterministic log
time reductions; consequently it complete for NC-1 under AC-0 reductions.
It follows that the Boolean formula value problem is not in the log time
hierarchy.
--
Jim Clarke -- Dept. of Computer Science, Univ. of Toronto, Canada M5S 1A4
(416) 978-4058
{allegra,cornell,decvax,linus,utzoo}!utcsri!clarke