Does the halting oracle separate P from NP?

15 views
Skip to first unread message

Newberry

unread,
Aug 4, 2022, 10:15:32 AM8/4/22
to
Does the halting oracle separate P from NP?

B.H.

unread,
Aug 4, 2022, 12:38:03 PM8/4/22
to
On Thursday, August 4, 2022 at 10:15:32 AM UTC-4, Newberry wrote:
> Does the halting oracle separate P from NP?

No, P^H = NP^H . In general, think of NP as a subset of EXP, which is a deterministic class that also has enough time to query the oracle for any language in H...both P and NP/EXP can run for at least one step to access the oracle for whatever problem in H. So ultimately, you get the same languages...P^H = NP^H = H.

-Philip White (philip...@yahoo.com)

Newberry

unread,
Aug 5, 2022, 8:49:57 PM8/5/22
to
But halting is the hardest problem. So it should be harder than the
Solovay oracle, should it not?
Reply all
Reply to author
Forward
0 new messages