|Mittagsseminar Talk Information|
Date and Time: Tuesday, September 18, 2012, 12:15 pm
Duration: 30 minutes
Location: CAB G51
Speaker: Robin Künzler
Does SAT have a Checker?
Suppose some efficient algorithm A solves SAT correctly on most inputs. A weak checker for SAT is an efficient algorithm that uses A to solve SAT correctly on *any* input with high probability. Unfortunately, for a broad class of weak checkers it is known that they do not work for SAT (unless the polynomial hierarchy collapses). These results have interesting connections to the following two problems:
1) Timon claims he found an efficient algorithm that solves SAT. Unfortunately, he does not (yet) have a proof for this claim. Is it possible to find an efficient program checker that checks the correctness of his algorithm on any given instance?
2) If one-way functions were proved to exist, cryptographers would be very happy as one could securely sign, encrypt, and so on. Showing the existence of one-way functions seems difficult, as it implies P not equal NP. But is it possible to show that P not equal NP implies that one-way functions exist?
In my talk I will explain these two problems and discuss how they are related to the weak checkability of SAT.
Upcoming talks | All previous talks | Talks by speaker | Upcoming talks in iCal format (beta version!)
Previous talks by year: 2013 2012 2011 2010 2009 2008 2007 2006 2005 2004 2003 2002 2001 2000 1999 1998 1997 1996
Information for students and suggested topics for student talks
Automatic MiSe System Software Version 1.3392 | admin login