3 ms·
They're not supposed to be; the goal was to give Jews harder questions which had supposedly simple answers: > One of the methods they used for doing this was t
by capnrefsmmat 15y ago
They're not supposed to be; the goal was to give Jews harder questions which had supposedly simple answers:
> One of the methods they used for doing this was to give the unwanted students a different set of problems on their oral exam. I was told that these problems were carefully designed to have elementary solutions (so that the Department could avoid scandals) that were nearly impossible to find.
- DanielRibeiro 15y agoThey could also give huge boolean formulas, and ask the applicant to decide if it is satisfiable[1] or not. Simple yes or no answer, which is quite a hard (NP-hard) to come by. But then again, it would probably fool nobody. [1] http://en.wikipedia.org/wiki/Boolean_satisfiability_problem http://en.wikipedia.org/wiki/Boolean_satisfiability_problem
- madars 15y agoWhile it is obvious that a satisfiable instance will have a simple yes-certificate, it is not known if for any unsatisfiable instance there is a short no-certificate (i.e. SAT is in NP, but believed not to be in coNP). The Jewish problems had to have simple solutions, while it could be hard to find a small proof of unsatisfiability of some large formula.