**Problem of the Week**

**BUGCAT**

**Zassenhaus Conference**

**Hilton Memorial Lecture**

**BingAWM**

**Math Club**

**Actuarial Association**

You are here: Homepage » Colloquium, Seminars, and Lecture Series » Combinatorics Seminar » abstract.202002dob

seminars:comb:abstract.202002dob

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.

seminars/comb/abstract.202002dob.txt · Last modified: 2020/05/17 22:18 by zaslav

Except where otherwise noted, content on this wiki is licensed under the following license: CC Attribution-Noncommercial-Share Alike 3.0 Unported