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

Groups > comp.lang.c++ > #119467

Re: Improved ℙ≠ℕℙ proof

Show all headers | View raw

On Thu, 2024-06-13 at 11:08 +0200, Bonita Montero wrote:
> Philosophizing makes you confuse

P!=NP is easy to understand for programmers.
Theory-making (academic) people get confused. I think in pragmatic way.

-----------------------
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]
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 simplicity, assume this temp_anp(q) computes a ℕℙℂ problem. 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(q2,I) 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 ℙ≠ℕℙ.

          IOW, for a ℕℙℂ problem, if the algorithm for one size-1-subproblem
          (complexity is irrelevant) does not provide information for another,
          (the remaining) size-1-subproblem, then the algorithm solving the ℕℙℂ
          problem must take at least O(2^N) steps.
-----------------------------------------------------------------------------

Back to comp.lang.c++ | Previous | Next — Previous in thread | Find similar

Thread

Improved ℙ≠ℕℙ proof wij <wyniijj5@gmail.com> - 2024-06-03 22:32 +0800
  Re: Improved ℙ≠ℕℙ proof wij <wyniijj5@gmail.com> - 2024-06-03 23:05 +0800
    Re: Improved ℙ≠ℕℙ proof wij <wyniijj5@gmail.com> - 2024-06-06 12:44 +0800
  Re: Improved ℙ≠ℕℙ proof Bonita Montero <Bonita.Montero@gmail.com> - 2024-06-13 11:08 +0200
    Re: Improved ℙ≠ℕℙ proof wij <wyniijj5@gmail.com> - 2024-06-13 19:03 +0800

csiph-web