| Deutsch English Français Italiano |
|
<87ikyg34s9.fsf@bsb.me.uk> View for Bookmarking (what is this?) Look up another Usenet article |
Path: ...!weretis.net!feeder8.news.weretis.net!eternal-september.org!feeder3.eternal-september.org!news.eternal-september.org!.POSTED!not-for-mail From: Ben Bacarisse <ben@bsb.me.uk> Newsgroups: comp.theory Subject: Re: Is this =?utf-8?B?4oSZ4omg4oSV4oSZ?= proof 'humiliating'? Date: Mon, 10 Jun 2024 21:45:58 +0100 Organization: A noiseless patient Spider Lines: 63 Message-ID: <87ikyg34s9.fsf@bsb.me.uk> References: <e243777ead89baebc46eac4944e43adde8a9ddce.camel@gmail.com> <875xuh51rv.fsf@bsb.me.uk> <0ae353a37b1dcf2926997ff00f7770999ee28b79.camel@gmail.com> <87zfrt3cz8.fsf@bsb.me.uk> <7f6d7e92eef8b68407f931fd3242cdcc1cd946c1.camel@gmail.com> MIME-Version: 1.0 Content-Type: text/plain; charset=utf-8 Content-Transfer-Encoding: 8bit Injection-Date: Mon, 10 Jun 2024 22:45:59 +0200 (CEST) Injection-Info: dont-email.me; posting-host="b018a74a51e8de81a68590f7334ceb3f"; logging-data="660536"; mail-complaints-to="abuse@eternal-september.org"; posting-account="U2FsdGVkX19qbS8ZLnF5Uqp5+D982/8chblhkoxSs6s=" User-Agent: Gnus/5.13 (Gnus v5.13) Cancel-Lock: sha1:astBJf65QfHWudG0fI11OPzjuPU= sha1:cNxy57IUd0iWFeBneN3YD7xEnwo= X-BSB-Auth: 1.54da2740d2405ab7bba5.20240610214558BST.87ikyg34s9.fsf@bsb.me.uk Bytes: 3922 wij <wyniijj5@gmail.com> writes: > On Mon, 2024-06-10 at 00:36 +0100, Ben Bacarisse wrote: >> wij <wyniijj5@gmail.com> writes: >> >> > On Sun, 2024-06-09 at 20:55 +0100, Ben Bacarisse wrote: >> > > wij <wyniijj5@gmail.com> writes: >> > > >> > > > ℙ≠ℕℙ >> > > > Proved. https://sourceforge.net/projects/cscall/files/MisFiles/PNP-proof-en.txt/download >> > > > ...[cut] >> > > > Proof2: Let p="Given a number n, determine whether or not n >> > > > is even". If >> > > > ℙ=ℕℙ, then p∉ℕℙℂ is a false proposition because all >> > > > ℕℙ problems >> > > > including ℕℙℂ are mutually Ptime reducible. Since >> > > > p∉ℕℙℂ is true, >> > > > ℙ≠ℕℙ is concluded. >> > > >> > > Where is your proof that p is not NP-complete? Since you don't know >> > > this subject very well, you would benefit more from asking people to >> > > direct you to resources from which you could learn, rather than posting >> > > provocative messages. >> >> <silly insults deleted> >> >> > To be on topic, can you show us the p (as mentioned) is NPC or p is >> > not NPC, either will do, to prove how much you understand what you >> > talked about. >> >> If I could do that I would be rich, quite literally. Sadly, I can't and >> neither can anyone else on the planet (so far). But if you think you >> can, head over to the Clay Mathematics Institute and persuade them to >> give you a million dollars[1]. >> >> For the hard-of-understanding, a proof that p, which is obviously in P, >> is also in NPC would immediately prove that P=NP. Alternatively, a >> proof that p is not in NPC would immediately prove that P=/=NP. >> >> [1] https://www.claymath.org/millennium/p-vs-np/ > > Probably I should make the Proof2 more formal: > > If p∈ℕℙℂ, then ℙ=ℕℙ and the concept of ℕℙℂ is useless. Correct, though uselessness is not a property that is provable. > If p∉ℕℙℂ, then ℙ=ℕℙ will be a contradiction (leads to p∈ℕℙℂ), so ℙ≠ℕℙ > is true in this case. No. If p∉ℕℙℂ, then ℙ=ℕℙ is false, i.e. P≠ℕℙ. There is no contradiction. You cannot conclude that this leads to p∈ℕℙℂ. That's why in your "less formal" argument you just stated it as an unproven fact. > Summary: Because ℕℙℂ is considered not useless, therefore ℙ≠ℕℙ is > concluded. ℕℙℂ is interesting only because it's that part of ℕℙ that might not be in ℙ. Once the question is settled, it stops being interesting. -- Ben.