Problem of the Week
BUGCAT
Zassenhaus Conference
Hilton Memorial Lecture
BingAWM
Math Club
In “A Framework for robust realistic geometric computations” by Erickson, van der Hoog, and Miltzow, the authors introduce a real analog of NP defined as those decision problems where every positive instance has a witness consisting of both bits and real numbers that can be verified in polynomial time in the real RAM model of computation. They show that such a problem can be reduced in polynomial time on a Turing machine to deciding whether a multivariate polynomial formula has a real solution. This is analogous to the Cook–Levin Theorem, which shows that every problem in NP can be reduced in polynomial time to deciding whether a Boolean formula has a satisfying assignment.