Differences

This shows you the differences between two versions of the page.

--- seminars:comb:abstract.202002dob [2020/05/18 02:18] – [Title:] zaslav
+++ seminars:comb:abstract.202002dob [2020/05/18 02:18] (current) – [Combinatorics Seminar,] zaslav
@@ Line 1: / Line 1: @@
+======  ======
+======  ======
+====== Speaker: Michael Dobbins (Binghamton) ======
+====== Title: The Real RAM Analogue to the Cook--Levin Theorem ======
+===== Combinatorics Seminar, Tuesday, February 11, 2020 =====
+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.