Rocksolid Light

Welcome to novaBBS (click a section below)

mail  files  register  newsreader  groups  login

Message-ID:  

The truth of a proposition has nothing to do with its credibility. And vice versa.


devel / comp.theory / Re: Does the halting oracle separate P from NP?

SubjectAuthor
* Does the halting oracle separate P from NP?Newberry
`* Does the halting oracle separate P from NP?B.H.
 `- Does the halting oracle separate P from NP?Newberry

1
Does the halting oracle separate P from NP?

<tcgka2$2qvtn$2@dont-email.me>

 copy mid

https://www.novabbs.com/devel/article-flat.php?id=36689&group=comp.theory#36689

 copy link   Newsgroups: comp.theory
Path: i2pn2.org!i2pn.org!eternal-september.org!reader01.eternal-september.org!.POSTED!not-for-mail
From: newberr...@gmail.com (Newberry)
Newsgroups: comp.theory
Subject: Does the halting oracle separate P from NP?
Date: Thu, 04 Aug 2022 07:15:28 -0700
Organization: A noiseless patient Spider
Lines: 1
Message-ID: <tcgka2$2qvtn$2@dont-email.me>
MIME-Version: 1.0
Content-Type: text/plain; charset=ISO-8859-1; format=flowed
Content-Transfer-Encoding: 7bit
Injection-Date: Thu, 4 Aug 2022 14:15:30 -0000 (UTC)
Injection-Info: reader01.eternal-september.org; posting-host="c241d25c6582e7e3e8644a5243602ae7";
logging-data="2981815"; mail-complaints-to="abuse@eternal-september.org"; posting-account="U2FsdGVkX1+0npWTPKkCFM8K5Y+xPR8LagpfCeyrArI="
User-Agent: Mozilla/5.0 (Windows NT 6.3; WOW64; rv:27.0) Gecko/20100101 Firefox/27.0 SeaMonkey/2.24
Cancel-Lock: sha1:DIOFf5LQNzKE0yztJz3U6jgDrg4=
X-Antivirus-Status: Clean
X-Antivirus: AVG (VPS 220804-0, 8/3/2022), Outbound message
 by: Newberry - Thu, 4 Aug 2022 14:15 UTC

Does the halting oracle separate P from NP?

Re: Does the halting oracle separate P from NP?

<e11c9f5b-ce49-4b42-8d92-3be0ad50058fn@googlegroups.com>

 copy mid

https://www.novabbs.com/devel/article-flat.php?id=36693&group=comp.theory#36693

 copy link   Newsgroups: comp.theory
X-Received: by 2002:a05:620a:448a:b0:6b8:e0cc:69f1 with SMTP id x10-20020a05620a448a00b006b8e0cc69f1mr2022032qkp.459.1659631081896;
Thu, 04 Aug 2022 09:38:01 -0700 (PDT)
X-Received: by 2002:a81:740a:0:b0:31f:3dea:2a47 with SMTP id
p10-20020a81740a000000b0031f3dea2a47mr2377592ywc.105.1659631081562; Thu, 04
Aug 2022 09:38:01 -0700 (PDT)
Path: i2pn2.org!i2pn.org!weretis.net!feeder6.news.weretis.net!1.us.feeder.erje.net!3.us.feeder.erje.net!feeder.erje.net!border-1.nntp.ord.giganews.com!nntp.giganews.com!news-out.google.com!nntp.google.com!postnews.google.com!google-groups.googlegroups.com!not-for-mail
Newsgroups: comp.theory
Date: Thu, 4 Aug 2022 09:38:01 -0700 (PDT)
In-Reply-To: <tcgka2$2qvtn$2@dont-email.me>
Injection-Info: google-groups.googlegroups.com; posting-host=173.53.104.152; posting-account=X_pe-goAAACrVTtZeoCLt7hslVPY2-Uo
NNTP-Posting-Host: 173.53.104.152
References: <tcgka2$2qvtn$2@dont-email.me>
User-Agent: G2/1.0
MIME-Version: 1.0
Message-ID: <e11c9f5b-ce49-4b42-8d92-3be0ad50058fn@googlegroups.com>
Subject: Re: Does the halting oracle separate P from NP?
From: xlt....@gmail.com (B.H.)
Injection-Date: Thu, 04 Aug 2022 16:38:01 +0000
Content-Type: text/plain; charset="UTF-8"
Content-Transfer-Encoding: quoted-printable
Lines: 9
 by: B.H. - Thu, 4 Aug 2022 16:38 UTC

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 (philipjwhite@yahoo.com)

Re: Does the halting oracle separate P from NP?

<tckdri$3f2kr$1@dont-email.me>

 copy mid

https://www.novabbs.com/devel/article-flat.php?id=36765&group=comp.theory#36765

 copy link   Newsgroups: comp.theory
Path: i2pn2.org!i2pn.org!eternal-september.org!reader01.eternal-september.org!.POSTED!not-for-mail
From: newberr...@gmail.com (Newberry)
Newsgroups: comp.theory
Subject: Re: Does the halting oracle separate P from NP?
Date: Fri, 05 Aug 2022 17:49:37 -0700
Organization: A noiseless patient Spider
Lines: 10
Message-ID: <tckdri$3f2kr$1@dont-email.me>
References: <tcgka2$2qvtn$2@dont-email.me> <e11c9f5b-ce49-4b42-8d92-3be0ad50058fn@googlegroups.com>
MIME-Version: 1.0
Content-Type: text/plain; charset=UTF-8; format=flowed
Content-Transfer-Encoding: 7bit
Injection-Date: Sat, 6 Aug 2022 00:49:54 -0000 (UTC)
Injection-Info: reader01.eternal-september.org; posting-host="e2ca355eb0631473bd34a373aa58ec1f";
logging-data="3639963"; mail-complaints-to="abuse@eternal-september.org"; posting-account="U2FsdGVkX18jApCJBOA8vWKFBvedH69+wmafho+qHVI="
User-Agent: Mozilla/5.0 (Windows NT 6.3; WOW64; rv:27.0) Gecko/20100101 Firefox/27.0 SeaMonkey/2.24
Cancel-Lock: sha1:U+UG+X+o9AETwU6aL682Mo9/tig=
X-Antivirus: AVG (VPS 220805-4, 8/5/2022), Outbound message
In-Reply-To: <e11c9f5b-ce49-4b42-8d92-3be0ad50058fn@googlegroups.com>
X-Antivirus-Status: Clean
 by: Newberry - Sat, 6 Aug 2022 00:49 UTC

B.H. wrote:
> 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 (philipjwhite@yahoo.com)

But halting is the hardest problem. So it should be harder than the
Solovay oracle, should it not?

1
server_pubkey.txt

rocksolid light 0.9.7
clearnet tor