דלג לתוכן (מקש קיצור 's')
Logo of Technion
Logo of CS Department
אירועים

אירועים

Theory Seminar: Lower Bounds for Satisfiability and Related Problems
event speaker icon
דיטר ואן מלקיבי (אונ. ויסקונסין)
event date icon
יום ראשון, 23.11.2008, 12:00
event location icon
חדר 601, בניין טאוב למדעי המחשב
Ever since the work of Cook and Levin, satisfiability has been recognized as a central problem in computational complexity. It is widely believed to be intractable, and yet till recently even a linear-time logarithmic-space algorithm was not ruled out.

The last few years have seen considerable progress in time-space lower bounds for satisfiability and closely related problems on various models of computation. This talk will describe the state-of-the-art on deterministic, randomized, and quantum machines, survey the underlying ideas, and present some of the arguments involved.
[בחזרה לאינדקס האירועים]