Deutsch English Français Italiano |
<71791c32465a478dd7d8d278dc2c4680b894c4c3.camel@gmail.com> View for Bookmarking (what is this?) Look up another Usenet article |
Path: ...!eternal-september.org!feeder3.eternal-september.org!news.eternal-september.org!.POSTED!not-for-mail From: wij <wyniijj5@gmail.com> Newsgroups: comp.lang.c Subject: Re: Improved =?UTF-8?Q?=E2=84=99=E2=89=A0=E2=84=95=E2=84=99?= proof Date: Thu, 06 Jun 2024 12:42:41 +0800 Organization: A noiseless patient Spider Lines: 19 Message-ID: <71791c32465a478dd7d8d278dc2c4680b894c4c3.camel@gmail.com> References: <933be7149a1cfdcd0abf2e7b793c20c8a00996ea.camel@gmail.com> <ec80bfdc7ee9ce8b143619f10c97eeb9d4ba6fe4.camel@gmail.com> <722b9f1dd968de561aa580a11d60bc03d95cb1c7.camel@gmail.com> MIME-Version: 1.0 Content-Type: text/plain; charset="UTF-8" Content-Transfer-Encoding: quoted-printable Injection-Date: Thu, 06 Jun 2024 06:42:42 +0200 (CEST) Injection-Info: dont-email.me; posting-host="9e19fa96b563737c16a53fa7a4d92a80"; logging-data="1446538"; mail-complaints-to="abuse@eternal-september.org"; posting-account="U2FsdGVkX1/USRo/i923ThXzB/Az3CTC" User-Agent: Evolution 3.50.2 (3.50.2-1.fc39) Cancel-Lock: sha1:1Bezs27s5DEghzVjpqTfHhzCyQg= In-Reply-To: <722b9f1dd968de561aa580a11d60bc03d95cb1c7.camel@gmail.com> Bytes: 1989 On Mon, 2024-06-03 at 23:06 +0800, wij wrote: =E2=84=99=E2=89=A0=E2=84=95=E2=84=99 Proved. https://sourceforge.net/projec= ts/cscall/files/MisFiles/PNP-proof-en.txt/download ....[cut] Note: Another super short proof that =E2=84=99=E2=89=A0=E2=84=95=E2=84= =99 (might be less constructive). Proof: If =E2=84=99=3D=E2=84=95=E2=84=99, then =E2=84=95=E2=84=99=E2=84= =82=3D=E2=84=99. All the problems in =E2=84=95=E2=84=99 are Ptime reduciabl= e. That means all the proofs that prove "Decide whether or not a gi= ven number is even" is not a =E2=84=95=E2=84=99=E2=84=82 are false p= roofs. Since such proofs are considered valid, =E2=84=95=E2=84=99=E2=84=82 and =E2=84=99 is n= ot the same, therefore, =E2=84=99=E2=89=A0=E2=84=95=E2=84=99.