Path: ...!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 NPC useless?
Date: Wed, 12 Jun 2024 11:10:33 +0100
Organization: A noiseless patient Spider
Lines: 88
Message-ID: <87ikyezd2e.fsf@bsb.me.uk>
References: <296ed519c7d2c9bfac06dc145f40fbabf765a3be.camel@gmail.com>
	<877cev3gpz.fsf@bsb.me.uk>
	<8ede5c7eb5a672de9bdaea8e7e4d038a8abc5194.camel@gmail.com>
	<87msnr12x9.fsf@bsb.me.uk>
	<0d73304fc3338e55da8bf0cde290279551471098.camel@gmail.com>
MIME-Version: 1.0
Content-Type: text/plain; charset=utf-8
Content-Transfer-Encoding: 8bit
Injection-Date: Wed, 12 Jun 2024 12:10:33 +0200 (CEST)
Injection-Info: dont-email.me; posting-host="0aad59004189f766bcfedb04f35e75b3";
	logging-data="1690310"; mail-complaints-to="abuse@eternal-september.org";	posting-account="U2FsdGVkX19QVYPqZsMzG4QDDVzvKDKqjP6PqfbftNk="
User-Agent: Gnus/5.13 (Gnus v5.13)
Cancel-Lock: sha1:yZ6hxFnovsFArvpftpBvdipzVfs=
	sha1:dizY6+QltImtd3SkVK9GVzwy85w=
X-BSB-Auth: 1.df911296aa17288de989.20240612111033BST.87ikyezd2e.fsf@bsb.me.uk
Bytes: 5647

wij <wyniijj5@gmail.com> writes:

> On Wed, 2024-06-12 at 00:21 +0100, Ben Bacarisse wrote:
>> wij <wyniijj5@gmail.com> writes:
>> 
>> > On Tue, 2024-06-11 at 11:40 +0100, Ben Bacarisse wrote:
>> > > wij <wyniijj5@gmail.com> writes:
>> > > 
>> > > > NPC specifies a set of very significant problems, and identifies such
>> > > > problems.  So, is very useful. But, let p="Determin whether a given
>> > > > number n is 5". If NPC cannot exclude p in NPC, what is the usefulness
>> > > > of NPC?
>> > > 
>> > > You've just explained why it's useful.  It's at the heart of the P/NP
>> > > question -- almost literally.  You hypothesise that "NPC cannot exclude
>> > > p in NPC" but we don't know that.  That's the core of the problem you
>> > > thought you had (or at least claimed to have) solved.
>> > 
>> > The problem is: If the problem whether or not p is a NPC cannot be
>> > proved, then all those proofs proving problems, say q, is not NPC must
>> > be false proofs.  Because that q must be Ptime reduciable between p.
>> 
>> Correct.  As of this moment, all purported proofs that "q is not in NPC"
>> are invalid.  Any such proof would be of huge significance and would be
>> published with great fanfare.  None are known to me at this time.
>> 
>> > To be spedific, proving problem p cannot be reduced to problem SAT
>> > is obvious
>> > to me. Just by actually programming it, not by abstract deduction, no
>> > info. there.
>> 
>> That's fine (though you have the reduction the wrong way round).  I have
>> no objection to you being sure of something as yet unproven.
>> 
>
> The Proof2 above was removed (flawed), because it still relies on the
> previous proof  but adds confusion:
>
> ------------------------
> This file is intended a proof that ℙ≠ℕℙ. The contents may be updated anytime.
> https://sourceforge.net/projects/cscall/files/MisFiles/PNP-proof-en.txt/download
> ...[cut]
> Prop1: ANP problem can be divided into two size-1-subproblems.
>    Proof: By spliting the certificate as follow:
>           bool temp_anp(Problem q) {
>             if(q.certificate().size()<Thresh) { // Thresh is a small constant
>               return solve_thresh_case(q);
>             }
>             Problem q1,q2;
>             split_certificate(q,q1,q2);        // Split the certificate in q
>             return temp_anp(q1) || temp_anp(q2); // to form q1,q2
>           }
>
> Prop2: ℙ≠ℕℙ
>    Proof: The temp_anp(q) can be re-written as follow:
>           bool temp_anp(Problem q) {
>             if(q.certificate().size()<Thresh) { // Thresh is a small constant
>               return solve_thresh_case(q);
>             }
>             Problem q1,q2;
>             split_certificate(q,q1,q2);  // Split the certificate in q to
>                                          //   disjoint subproblem q1, q2.
>             Info I;                      // I=info. that helps solving q
>             if(temp_anp_i(q1,I)==true) { // temp_anp_i(q1,I) solves temp_anp(q1)
>                                          // and stores whatever helpful into I
>               return true;
>             }
>             return solv_remain(q2,I);    // Solve temp_anp(q2) with the given I
>           }
>
>           For a ℕℙℂ problem q, if ℙ=ℕℙ, then information I is unnecessary for
>           solv_remain(q2,I) because it can compute I in Ptime by its own. Thus,
>           the complexity of solv_remain(..) is equivalent to the independent
>           size-1-subproblem temp_anp(q2) (if not equivalent, the general
>           recursive algorithms of solving ℕℙℂ and Prop1 are wrong, which is not
>           the fact). Equally, temp_anp_i(q1,I) is then equivalent to the
>           size-1-subproblem temp_anp(q1) simply by not providing I. Therefore,
>           the complexity of temp_anp(q) is W(|q|)= W(|q|-1)+W(|q|-1)=
>           2^(|q|-1)*W(1), W(1)>=1, a O(2^N) level of complexity contradicting
>           the assumed Ptime. Therefore, from ℕℙℂ≠ℙ, we can conclude ℙ≠ℕℙ.
> -----------------------------------------------------------------------------

You are missing any step that allows one to conclude that ℙ≠ℕℙ.  What
you appear to be proving (that from ℕℙℂ≠ℙ, we can conclude ℙ≠ℕℙ) is a
known theorem, but there are much simpler ways to show it.

-- 
Ben.