most recent 30 from http://mathoverflow.net 2013-05-25T02:29:04Z http://mathoverflow.net/feeds/user/7011 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/57965/oracle-relativization-and-p-vs-np-philosophical/57988#57988 MassimoLauria 2011-03-09T19:53:25Z 2011-03-09T19:53:25Z

<p>In the case you are interested, adding an oracle for a language $B$ to a machine means that such machine is able to do some non-trivial computation at cost of one atomic operation (ignoring the resources needed to prepare the query to the oracle). This make such machine more powerful (maybe not strictly ...). </p> <p>It is quite possible that a polynomial time <strong>non-deterministic</strong> machine $N$ can harness such power in ways that a mere <strong>deterministic</strong> machine $D$ cannot. That would mean that in presence of such oracle for $B$, the computational speed-up for $N$ is larger than the one for $D$.</p>