## The Abundance of Oracles for which P=NP |

**Nikhil Srivastava**

Union College

April 22, 2005

4:30 pm

Golub 105

Pizza and drinks will be served

P=?NP is the most important open question in computer science. It asks, roughly, if all computational problems for which solutions can be guessed/checked quickly can also be solved quickly, or equivalently, whether or not there is any intrinsic difficulty to problems that seem to require brute force search. A crucial concept in the study of this question has been that of an oracle. Intuitively, an oracle provides solutions to some computational problems for free; for example, an oracle for Traveling Salesman (TSP) would (almost) instantly give a minimal tour for any graph. It is evident that an oracle for a hard problem such as TSP can provide a great deal of computational power, and may effect whether P=NP. This is indeed the case; in fact, it is known that there are oracles relative to which P equals NP and oracles relative to which P does not equal NP. In this talk, we will touch upon results in the literature showing that P=NP for only a "small" set of oracles, under two different notions of "small," and then describe an attempt to prove a similar result for a third notion of "small."

For additional information, send e-mail to math@union.edu or call (518) 388-6246.

Union College Math Department Home PageComments to: math@union.edu Created automatically on: Fri Apr 20 00:47:10 EDT 2018 |