Re: Is this ℙ≠ℕℙ proof 'humiliating'?

From	Ben Bacarisse <ben@bsb.me.uk>
Newsgroups	comp.theory
Subject	Re: Is this ℙ≠ℕℙ proof 'humiliating'?
Date	2024-06-10 21:45 +0100
Organization	A noiseless patient Spider
Message-ID	<87ikyg34s9.fsf@bsb.me.uk> (permalink)
References	<e243777ead89baebc46eac4944e43adde8a9ddce.camel@gmail.com> <875xuh51rv.fsf@bsb.me.uk> <0ae353a37b1dcf2926997ff00f7770999ee28b79.camel@gmail.com> <87zfrt3cz8.fsf@bsb.me.uk> <7f6d7e92eef8b68407f931fd3242cdcc1cd946c1.camel@gmail.com>

Show all headers | View raw

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.

Back to comp.theory | Previous | Next — Previous in thread | Find similar | Unroll thread

Thread

Is this ℙ≠ℕℙ proof 'humiliating'? wij <wyniijj5@gmail.com> - 2024-06-08 22:11 +0800
  Re: Is this ℙ≠ℕℙ proof 'humiliating'? wij <wyniijj5@gmail.com> - 2024-06-08 22:17 +0800
  Re: Is this ℙ≠ℕℙ proof 'humiliating'? Ben Bacarisse <ben@bsb.me.uk> - 2024-06-09 20:55 +0100
    Re: Is this ℙ≠ℕℙ proof 'humiliating'? wij <wyniijj5@gmail.com> - 2024-06-10 05:58 +0800
      Re: Is this ℙ≠ℕℙ proof 'humiliating'? Andy Walker <anw@cuboid.co.uk> - 2024-06-09 23:57 +0100
        Re: Is this ℙ≠ℕℙ proof 'humiliating'? wij <wyniijj5@gmail.com> - 2024-06-10 08:06 +0800
          Re: Is this ℙ≠ℕℙ proof 'humiliating'? Andy Walker <anw@cuboid.co.uk> - 2024-06-10 14:54 +0100
            Re: Is this ℙ≠ℕℙ proof 'humiliating'? wij <wyniijj5@gmail.com> - 2024-06-10 22:33 +0800
      Re: Is this ℙ≠ℕℙ proof 'humiliating'? Ben Bacarisse <ben@bsb.me.uk> - 2024-06-10 00:36 +0100
        Re: Is this ℙ≠ℕℙ proof 'humiliating'? wij <wyniijj5@gmail.com> - 2024-06-10 08:12 +0800
          Re: Is this ℙ≠ℕℙ proof 'humiliating'? Ben Bacarisse <ben@bsb.me.uk> - 2024-06-10 21:50 +0100
            Re: Is this ℙ≠ℕℙ proof 'humiliating'? wij <wyniijj5@gmail.com> - 2024-06-11 12:37 +0800
              Re: Is this ℙ≠ℕℙ proof 'humiliating'? Jeff Barnett <jbb@notatt.com> - 2024-06-11 00:32 -0600
                Re: Is this ℙ≠ℕℙ proof 'humiliating'? wij <wyniijj5@gmail.com> - 2024-06-11 16:01 +0800
              Re: Is this ℙ≠ℕℙ proof 'humiliating'? Ben Bacarisse <ben@bsb.me.uk> - 2024-06-11 11:43 +0100
        Re: Is this ℙ≠ℕℙ proof 'humiliating'? wij <wyniijj5@gmail.com> - 2024-06-10 22:26 +0800
          Re: Is this ℙ≠ℕℙ proof 'humiliating'? Ben Bacarisse <ben@bsb.me.uk> - 2024-06-10 21:45 +0100

csiph-web