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