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

Groups > comp.lang.c > #385464

Re: Improved ℙ≠ℕℙ proof

Show all headers | View raw

On Mon, 2024-06-03 at 22:26 +0800, wij wrote:
> The P!=NP proof should be completed.
> The updated proof may even be shorter, intuitive and robust !!!
> ---------------------------------------------------------------
> 
> 
> 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
> 
> -----------------------------------------------------------------------------
> Algorithmic problem::= Problems that can be processed by asymptotic analysis.
> 
> ANP::= Another NP is a set defined as {q| q is a description of the algorithmic
>    decision problem that provides 1. A set of certificate data C 2. A Ptime
>    (Polynomial time) verification method v 3. The answer of q is 'yes' iff
>    there exists a certificate c, c∈C, such that v(c) is true 4. q can be
>    computed in at most O(2^|q|) steps. }.
>    More precisely, ANP is the set of problems that can be solved by the 
>    following pseudo-C/C++ program temp_anp(q):
> 
>    bool temp_anp(Problem q) {           // Problem: Description of the problem
>      Certificate c,begin,end;           // Certificate data can be accessed by
>      begin= get_begin_certificate(q);   //   iteration, at least.
>      end  = get_end_certificate(q);
>      for(c=begin; c!=end; c=next(c)) {  // O(2^|n|) loop (see Note2)
>        if(v(c)) return true;            // v:Certificate->{true,false}, Ptime
>                                         //      verification function.
>      }
>      return false;
>    }
> 
>    Note1: Relative to the Turing Machine language for ℕℙ, the reason using
>          pseudo-C/C++ is that 1.C-code (almost all high level programming
>          language not involving special hardware features) and TM language are
>          computationally interchangeable. 2.It describes the problem more
>          clearly (but not always) 3.The result 'false' is visible 4. ℕℙ
>          definition does not say the certificate C and the verication v are
>          given, fixed arguments. In ANP, v(c) is explicitly spedified a Ptime
>          function 5.Easier for machine aided verification.
> 
>    Note2: The semantics of the for loop in temp_anp(q) includes nested loops for
>          sets like C=C1×C2×C3×...
> 
> Polynomial time procedure::= (or polynomial time function) A procedure composed
>    of sequential execution of O(P) number of fixed-time procedures.
>    (Therefore, O(P) number of sequential Ptime procedure is equivalent to a
>    single Ptime procedure)
> 
> Size-1-subproblem::= The problem whose size of input is less by one than that
>    of the orginal problem.
> 
> Theorem: 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
>           }
> 
> Assume solving some ANP problem by temp_anp(q) whose size-1-subproblem
> temp_anp(q1) is solved, then the remaining task has one more information I
> (i.e. whatever the computaion of temp_anp(q1) can provide) to reduce the
> workload of solving the remaining task, and defined as solve_remain(q2,I).
> If ℙ=ℕℙ, which means the remaining task can be completed independently in Ptime
> without I. In this sitution, solve_remain(q2,I) is equivalent to temp_anp(q2).
> But the complexity of computation is W(|q|)=W(|q|-1)+ W(|q|-1)= 2^(|q|-1)*W(1),
> a O(2^N) level of complexity contradicting he assumed Ptime. Therefore, ℙ≠ℕℙ.
> -----------------------------------------------------------------------------

A typo in the last paragraph:


Assume solving some ℕℙℂ problem by temp_anp(q) whose size-1-subproblem
temp_anp(q1) is solved, then the remaining task has one more information I
(i.e. whatever the computaion of temp_anp(q1) can provide) to reduce the
workload of solving the remaining task, and defined as solve_remain(q2,I).
If ℙ=ℕℙ, which means the remaining task can be completed independently in Ptime
without I. In this sitution, solve_remain(q2,I) is equivalent to temp_anp(q2).
But the complexity of computation is W(|q|)=W(|q|-1)+ W(|q|-1)= 2^(|q|-1)*W(1),
a O(2^N) level of complexity contradicting the assumed Ptime. Therefore, ℙ≠ℕℙ.

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

Thread

Improved ℙ≠ℕℙ proof wij <wyniijj5@gmail.com> - 2024-05-30 17:18 +0800
  Re: Improved ℙ≠ℕℙ proof wij <wyniijj5@gmail.com> - 2024-05-31 23:13 +0800
  Re: Improved ℙ≠ℕℙ proof wij <wyniijj5@gmail.com> - 2024-06-03 22:26 +0800
    Re: Improved ℙ≠ℕℙ proof wij <wyniijj5@gmail.com> - 2024-06-03 23:06 +0800
      Re: Improved ℙ≠ℕℙ proof wij <wyniijj5@gmail.com> - 2024-06-06 12:42 +0800

csiph-web