novaBBS - comp.theory - Re: ℙ≠ℕℙ (solved)

ℙ≠ℕℙ (solved)

<ebc7bfa7-22ef-4308-bed4-c0e5b5b86567n@googlegroups.com>

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

X-Received: by 2002:a0c:ef0a:0:b0:4bc:158d:faf6 with SMTP id t10-20020a0cef0a000000b004bc158dfaf6mr175080qvr.11.1669054264706;
Mon, 21 Nov 2022 10:11:04 -0800 (PST)
X-Received: by 2002:ac8:4789:0:b0:3a5:1d64:96de with SMTP id
k9-20020ac84789000000b003a51d6496demr302631qtq.383.1669054264417; Mon, 21 Nov
2022 10:11:04 -0800 (PST)
Path: i2pn2.org!i2pn.org!usenet.blueworldhosting.com!feed1.usenet.blueworldhosting.com!peer02.iad!feed-me.highwinds-media.com!news.highwinds-media.com!news-out.google.com!nntp.google.com!postnews.google.com!google-groups.googlegroups.com!not-for-mail
Newsgroups: comp.theory
Date: Mon, 21 Nov 2022 10:11:04 -0800 (PST)
Injection-Info: google-groups.googlegroups.com; posting-host=124.218.76.41; posting-account=0Ek0TQoAAAAS0oceh95IuNV59QuIWNeN
NNTP-Posting-Host: 124.218.76.41
User-Agent: G2/1.0
MIME-Version: 1.0
Message-ID: <ebc7bfa7-22ef-4308-bed4-c0e5b5b86567n@googlegroups.com>
Subject: ℙ≠ℕℙ (solved)
From: wynii...@gmail.com (wij)
Injection-Date: Mon, 21 Nov 2022 18:11:04 +0000
Content-Type: text/plain; charset="UTF-8"
Content-Transfer-Encoding: quoted-printable
X-Received-Bytes: 1520

by: wij - Mon, 21 Nov 2022 18:11 UTC

I am happy to announce the ℙ≠ℕℙ problem can be succinctly solved.

Define: bool Sat(Prog): Sat(f)==true iff ∃f(x), f(x) returns in P-time.
Sat is a language interpreter. Prog is a pass-by-value argument (e.g. TM description).

1. Problem(Sat)∈ℕℙ (from definition)
2. Problem(Sat)∉ℙ (from the HP proof, Sat will encounter an undecidable case)

Conclusion: ℙ≠ℕℙ

Re: ℙ≠ℕℙ (solved)

<87mt8knlts.fsf@bsb.me.uk>

copy mid

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

copy link Newsgroups: comp.theory

Path: i2pn2.org!i2pn.org!eternal-september.org!reader01.eternal-september.org!.POSTED!not-for-mail
From: ben.use...@bsb.me.uk (Ben Bacarisse)
Newsgroups: comp.theory
Subject: Re: ℙ≠ℕℙ (solved)
Date: Mon, 21 Nov 2022 19:34:23 +0000
Organization: A noiseless patient Spider
Lines: 29
Message-ID: <87mt8knlts.fsf@bsb.me.uk>
References: <ebc7bfa7-22ef-4308-bed4-c0e5b5b86567n@googlegroups.com>
MIME-Version: 1.0
Content-Type: text/plain; charset=utf-8
Content-Transfer-Encoding: 8bit
Injection-Info: reader01.eternal-september.org; posting-host="0b7422340e19e32d781009d919f3c74c";
logging-data="4066498"; mail-complaints-to="abuse@eternal-september.org"; posting-account="U2FsdGVkX1+iqDl/CfPXgClMY7ZfPZYH2mxouUxkIiQ="
User-Agent: Gnus/5.13 (Gnus v5.13) Emacs/27.1 (gnu/linux)
Cancel-Lock: sha1:lKClPuy3RodCnLad7kj57mKU+1w=
sha1:8mo7UXbUWo0b3THbFj4hdoej1wU=
X-BSB-Auth: 1.d91f779d5f82c5262b84.20221121193423GMT.87mt8knlts.fsf@bsb.me.uk

by: Ben Bacarisse - Mon, 21 Nov 2022 19:34 UTC

wij <wyniijj5@gmail.com> writes:

> I am happy to announce the ℙ≠ℕℙ problem can be succinctly solved.
>
> Define: bool Sat(Prog): Sat(f)==true iff ∃f(x), f(x) returns in
> P-time.

This line has at least one abuse of notation and probably other, but I
can't parse it. It looks more like a math poem than an actual
well-formed formula.

> Sat is a language interpreter. Prog is a pass-by-value argument
> (e.g. TM description).
>
> 1. Problem(Sat)∈ℕℙ (from definition)
> 2. Problem(Sat)∉ℙ (from the HP proof, Sat will encounter an
> undecidable case)

(a) There are no undecidable cases.

(b) If Problem(Sat) (whatever that means) is not in P because of the
undeciability of halting, then it's not in NP either.

> Conclusion: ℙ≠ℕℙ

No.

--
Ben.

!07/11 PDP a ni deppart m'I !pleH

devel / comp.theory / Re: ℙ≠ℕℙ (solved)

Subject	Author
ℙ≠ℕℙ (solved)	wij
ℙ≠ℕℙ (solved)	Ben Bacarisse