Re: Is NPC useless?

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.