Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.theory > #106976

Re: Is NPC useless?

Show all headers | View raw

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.

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

Thread

Is NPC useless? wij <wyniijj5@gmail.com> - 2024-06-11 13:47 +0800
  Re: Is NPC useless? Ben Bacarisse <ben@bsb.me.uk> - 2024-06-11 11:40 +0100
    Re: Is NPC useless? wij <wyniijj5@gmail.com> - 2024-06-11 19:46 +0800
      Re: Is NPC useless? Ben Bacarisse <ben@bsb.me.uk> - 2024-06-12 00:21 +0100
        Re: Is NPC useless? wij <wyniijj5@gmail.com> - 2024-06-12 17:01 +0800
          Re: Is NPC useless? Ben Bacarisse <ben@bsb.me.uk> - 2024-06-12 11:10 +0100

csiph-web