The Abundance of Oracles for which P=NP
April 22, 2005
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."
|Union College Math Department Home Page|
Comments to: email@example.com
Created automatically on: Tue Oct 23 16:15:50 EDT 2018