Prof. Emo Welzl and Prof. Bernd Gärtner
|Mittagsseminar Talk Information|
Date and Time: Tuesday, September 18, 2012, 12:15 pm
Duration: 30 minutes
Location: OAT S15/S16/S17
Speaker: Robin Künzler
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.
Automatic MiSe System Software Version 1.4803M | admin login