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

Groups > comp.lang.c++ > #123022 > unrolled thread

P!=NP proof, revised

Back to article view | Back to comp.lang.c++

Contents

  P!=NP proof, revised wij <wyniijj5@gmail.com> - 2025-11-19 15:23 +0800
    Re: P!=NP proof, revised wij <wyniijj5@gmail.com> - 2025-11-28 11:50 +0800
    Re: P!=NP proof, revised wij <wyniijj5@gmail.com> - 2025-12-11 23:38 +0800
      Re: P!=NP proof, revised wij <wyniijj5@gmail.com> - 2025-12-14 17:29 +0800

#123022 — P!=NP proof, revised

The following is a snipet of the revised proof
https://sourceforge.net/projects/cscall/files/MisFiles/PNP-proof-en.txt/download

I think the idea of the proof should be valid and easy to understand. The rest
technical apart should be straightforward (could take pages or dozens of pages,
so ignored). But, anyway, something like the C/C++ description is still needed.
Can you find any defects?

OTOH, C/C++ can be the language for for proving math. theorems, lots easier than
TM language to handle and understand. Opinions?

--------
ℕℙ::= {q| q is a decision problem that a computer solves in O(2^|q|) steps using
       the following fnp algorithm template. q contains a verification dataset
       C, card(C)∈O(2^|q|), and a Ptime verification function v:C->{true,false}.
       If ∃c,v(c)=true, then the answer to problem q is true; otherwise, it is
       false.}

    // begin_certificate is a Ptime function that retrieves the first
    // Certificate element from the problem statement q. If this element does
    // not exist, it returns a unique and virtual EndC element.
    Certificate begin_certificate(Problem q);

    // end_certificate is a Ptime function that retrieves the element EndC from
    // the problem statement q.
    Certificate end_certificate(Problem q);

    // next_certificate is a Ptime function that retrieves the next element of
    // c from the problem statement q. If this element does not exist, return
    // the EndC element.
    Certificate next_certificate(Problem q, Certificate c);

    // v is a Ptime function. v(c)==true if c is the element expected by the
    // problem.
    bool v(Certificate c);

    bool fnp(Problem q) {
      Certificate c, begin, end;   // Declare the verification data variable
      begin= begin_certificate(q); // begin is the first verification data
      end= end_certificate(q);     // end is the false data EndC used to
                                   // indicate the end.
      for(c = begin; c != end;
          c = next_certificate(q, c)) { // At most O(2^|q|) steps.
                                        // next_certificate(c) is the Ptime
                                        // function to get the next
                                        // verification data of c
          if(v(c) == true) return true; // v: C->{true, false} is the polynomial
                                        // time verification function.
      }
      return false;
    }

    Since a continuous O(P) number of Ptime functions (or instructions) can be
    combined into a single Ptime function, if the complexity of each function is
    Ptime, and the smallest unit of complexity is also Ptime, then it's roughly
    the same. Any Ptime function can be added, deleted, merged, or split in the
    algorithm without affecting the algorithm's complexity. Perhaps in the end,
    only the number of decision branches needs to be considered.

    [Note] This definition of ℕℙ is equivalent to the traditional Turing machine
           definition of ℕℙ. The proof of equivalence is plain and lengthy, and
           not very important to most people, so it is omitted.

    [Note] According to the Church-Turing conjecture, no formal language can
           surpass the expressive power of a Turing machine (or algorithm) (i.e.
           the decisive operational process from part to whole). C language can
           be regarded as a high-level language for Turing machines, and as a
           formal language for knowledge or proof.

Problem Q::= Given plaintext a, ciphertext b, decoder d, and key length klen.
    The key is a Ptime program. Problem Q determines whether there exists a
    key c such that d(b,c)=a.

    Problem Q can be computed using the following C/C++ pseudo code as fnp by
    definition; therefore, Q∈ℕℙ.
    Plaintext a, ciphertext b, decoder d, and the length of key klen are all
    obtained from q:

    bool f(Problem q) {
      int MaxKey= ...                  // klen=maximum value of key (O(2^klen))
      for(int c=1; c<=MaxKey; ++i) {
        if(equ(d(b,c),a)) return true; // Polynomial-time verification
                                       // (If c is not a valid program, then d
                                       // returns a value such that equ test
                                       // result is false)
      }
      return false;
    }

    Since the key is a freely written program, Each decription algorithm (key)
    is essentially independent, and the given problem q may contain no
    information about the algorithm's logic (knowledge of one key cannot be
    used to deduce information about another).
    Therefore, at least O(2^|klen|) possible key values must be tested one by
    one. Thus, the complexity of problem q is O(2^N).
---------------

(Thanks to olcott, this proof was origianlly inspired by POO Halt, where the
 P-NP proof based on Halting Problem was found invalid)

[toc] | [next] | [standalone]

#123101

On Wed, 2025-11-19 at 15:23 +0800, wij wrote:
> The following is a snipet of the revised proof
> https://sourceforge.net/projects/cscall/files/MisFiles/PNP-proof-en.txt/download
> 
> I think the idea of the proof should be valid and easy to understand. The rest
> technical apart should be straightforward (could take pages or dozens of pages,
> so ignored). But, anyway, something like the C/C++ description is still needed.
> Can you find any defects?
> 
> OTOH, C/C++ can be the language for for proving math. theorems, lots easier than
> TM language to handle and understand. Opinions?

-----------------------------------------------------------------------------
Algorithmic Problem::= A computer problem in which the computational steps are a
    function of the problem statement's length (size). This problem can be
    described asymptotically as the relationship between the problem size and
    the computational steps.

Polynomial-time procedure (or Ptime procedure)::= O(P) number of consecutive,
    fixed-sized basic operations (because the procedure is a deterministic
    process, it is sometimes called a "function" or "operation"). Therefore, as
    defined by O(P), O(P) number of Ptime procedures executed consecutively can
    also be considered as a single Ptime procedure.

Reduction::= The algorithm for computation problem A can be transformed into
    computation problem B by a Ptime procedure, denoted as A≤B (because the
    Ptime transformation itself includes the computation of problem A, any two
    Ptime problems can be reduced to each other).

ANP::= {q| q is a statement of a decision problem that a computer can solve in
    O(2^|q|) steps using the following fnp algorithm template. q contains a
    certification dataset C, card(C)∈O(2^|q|), and a Ptime verification function
    v:C->{true,false}. If ∃c,v(c)=true, then the answer to problem q is true;
    otherwise, it is false.}

    // begin_certificate is a Ptime function that retrieves the first
    // Certificate element from the problem statement q. If this element does
    // not exist, it returns a unique and virtual EndC element.
    Certificate begin_certificate(Problem q);

    // end_certificate is a Ptime function that retrieves the element EndC from
    // the problem statement q.
    Certificate end_certificate(Problem q);

    // next_certificate is a Ptime function that retrieves the next element of
    // c from the certification dataset C. If this element does not exist,
    // return the EndC element.
    Certificate next_certificate(Problem q, Certificate c);

    // v is a Ptime function. v(c)==true if c is the element expected by the
    // problem.
    bool v(Certificate c);

    bool fnp(Problem q) {
      Certificate c, begin, end;   // Declare the certification data variable
      begin= begin_certificate(q); // begin is the first certification data
      end= end_certificate(q);     // end is the false data EndC used to
                                   // indicate the end.
      for(c = begin; c != end;
          c = next_certificate(q, c)) { // At most O(2^|q|) steps.
                                        // next_certificate(c) is a Ptime
                                        // function to get the next
                                        // certification data of c
          if(v(c) == true) return true; // v: C->{true, false} is a polynomial
                                        // time verification function.
      }
      return false;
    }

    Since a continuous O(P) number of Ptime functions (or instructions) can be
    combined into a single Ptime function, at roughly this complexity analysis,
    any Ptime function can be added, deleted, merged/split in the algorithm
    steps without affecting the algorithm's complexity. Perhaps in the end, only
    the number of decision branches needs to be considered.

    An ANP problem q can be expressed as q<v, C>, where v = Ptime verification
    function, and C = certification dataset (description).

    [Note] According to Church-Turing conjecture, no formal language can
           surpass the expressive power of a Turing machine (or algorithm, i.e.,
           the decisive operational process from parts to the whole). C
           language can be regarded as a high-level language of Turing machines,
           and as a formal language for knowledge or proof.
                                                            
Prop1: ANP = ℕℙ
   Proof: Omitted (The proof of the equivalence of ANP and the traditional
          Turing machine definition of ℕℙ is straightforward and lengthy, and
          not very important to most people. Since there are already thousands
          of real-world ℕℙℂ problems available for verification, the definition
          of ANP does not rely on NDTM theory)

Prop2: An ANP problem q<v,C> can be arbitrarily partitioned into two subproblems
       q1<v,C1>, q2<v,C2), where C = C1∪C2.
   Proof: The certification dataset can be recursively partitioned as follows:

          bool banp(Problem q) {
            if(certificate_size(q)<Thresh) { // Thresh is a small constant
              return solve_thresh_case(q); // Solve q in constant time
            }
            Problem q1,q2;
            split_certificate(q,q1,q2); // Split the certification dataset C
                                        // to form q1,q2, in which the number of
                                        // certificates are roughly the same.
            return banp(q1) || banp(q2); // Compute the subproblems respectively
          }

Prop3: Any two ANP problems q1 and q2 can be synthesized into another ANP
       problem q, denoted as q = q1 ⊕ q2. The certification dataset C and the
       verification function v of q are defined as follows:

       C = C1 ∪ C2     // C1 and C2 are the certification datasets of q1 and q2
                       // respectively

       bool v(x) {
         return v1(x) || v2(x);  // v1 and v2 are the verification functions of
                                 // q1 and q2 respectively
       }

       Therefore, we have the identity: q1<v1,C1>⊕ q2<v2,C2> = q<v1||v2, C1∪C2>.

Prop4: ℙ=ℕℙ iff the algorithm fnp in the ℕℙ definition (or ℕℙℂ algorithm) can be
       replaced by a Ptime algorithm.
   Proof: Omitted

Prop5: For subproblems q1<v,C1> and q2<v,C2> (same v), if C1 ∩ C2 = ∅, then
       there is no information in problem q1 that is sufficient in terms of
       order of complexity to speed up the computation of q2.
   Proof: An AuxInfo object, called 'auxiliary information', can be added to
          banp to store the results after computation of a certain problem q,
          as rewritten as banp2. Depending on the content of the auxiliary
          information, banp2 can represent possible algorithms for ANP/ℕℙℂ
          problems with complexity ranging from O(N) to O(2^N).

        bool banp2(Problem q, AuxInfo* ibuf) { // Calculate q and write the
                                      // obtained auxiliary information to *ibuf
        // Check and initialize *ibuf
        if(certificate_size(q)<Thresh) {
          return solve_thresh_case(q,ibuf);
        }
        Problem q1,q2;
        split_certificate(q,q1,q2);
        AuxInfo I;               // I stores information to help solve problems.
        if(banp2(q1,&I)==true) { // banp2(q1,I) recursively computes subproblem
                                 // q1 and stores any auxiliary information that
                                 // can be derived from q1 in I.

          write_ibuf1(ibuf,q);   // Write auxiliary information
          return true;           // The information obtained from subproblem q1
                                 // is valid for any problem q.
        }
        bool rv=banp2_i(q2,I);   // Solve q2 with given information I, effective
                                 // regardless of the source of the problem.
        write_ibuf2(ibuf,q);
        return rv;
      }

      The above `banp2_i` does not care which ANP problem (including trivial
      problems) the given information `I` originates from. The `I` generated can
      also provide auxiliary information for almost all other ANP problems.

      Since the auxiliary information I obtained from the trivial subproblems
      cannot provide sufficient information to accelerate computation to the
      extent of improving the complexity order for every subproblem, the
      proposition is proved.

Conclusion: Since banp2 algorithm cannot be faster than O(2^N), there is no
      algorithm faster than O(2^N) for ℕℙℂ problems. Therefore, ℙ≠ℕℙ.

      [Note] In fact, from Prop4, the fnp definition of the ℕℙ problem, and the
             definition of the Ptime procedure, it can also be roughly seen that
             ℙ≠ℕℙ.
-----------------------

I feel the 'assertion' in Prop5 "the trivial subproblems cannot provide
      sufficient information to accelerate computation to the
      extent of improving the complexity order for every subproblem, the
      proposition is proved." is abrupt. Better way of phrasing?

[toc] | [prev] | [next] | [standalone]

#123135

The script of proof is formal enough to submit to professional institute, I think.
Anything unclear or defect?

The following is form https://sourceforge.net/projects/cscall/files/MisFiles/PNP-proof-en.txt/download

--------------------------------------------------------------------------------
Algorithmic Problem::= A computer problem in which the computational steps are a
    function of the problem statement's length (size). This problem can be
    described asymptotically as the relationship between the problem size and
    the computational steps.

Polynomial-time procedure (or Ptime procedure)::= O(P) number of consecutive,
    fixed-sized basic operations (because the procedure is a deterministic
    process, it is sometimes called a "function" or "operation"). Therefore, as
    defined by O(P), O(P) number of Ptime procedures executed consecutively can
    also be considered as a single Ptime procedure.

Reduction::= The algorithm for computation problem A can be transformed into
    computation problem B by a Ptime procedure, denoted as A≤B (because the
    Ptime transformation itself includes the computation of problem A, any two
    Ptime problems can be reduced to each other).

ANP::= {q| q is a statement of a decision problem that a computer can solve in
    O(2^|q|) steps using the following fnp algorithmic template. q contains a
    certification dataset C, card(C)<=O(2^|q|), and a Ptime verification
    function v:C->{true,false}. If ∃c,v(c)=true, then the answer to problem q is
    true; otherwise, it is false.}

    // begin_certificate is a Ptime function that retrieves the first
    // Certificate element from the problem statement q. If this element does
    // not exist, it returns a unique and virtual EndC element.
    Certificate begin_certificate(Problem q);

    // end_certificate is a Ptime function that retrieves the element EndC from
    // the problem statement q.
    Certificate end_certificate(Problem q);

    // next_certificate is a Ptime function that retrieves the next element of
    // c from the certification dataset C. If this element does not exist,
    // return the EndC element.
    Certificate next_certificate(Problem q, Certificate c);

    // v is a Ptime function. v(c)==true if c is the element expected by the
    // problem.
    bool v(Certificate c);

    bool fnp(Problem q) {
      Certificate c, begin, end;   // Declare the certification data variable
      begin= begin_certificate(q); // begin is the first certification data
      end= end_certificate(q);     // end is the false data EndC used to
                                   // indicate the end.
      for(c = begin; c != end;
          c = next_certificate(q, c)) { // At most O(2^|q|) steps.
                                        // next_certificate(c) is a Ptime
                                        // function to get the next
                                        // certification data of c
          if(v(c) == true) return true; // v: C->{true, false} is a polynomial
                                        // time verification function.
      }
      return false;
    }

    Since a continuous O(P) number of Ptime functions (or instructions) can be
    combined into a single Ptime function, at roughly this complexity analysis,
    any Ptime function can be added, deleted, merged/split in the algorithm
    steps without affecting the algorithm's complexity. Perhaps in the end, only
    the number of decision branches needs to be considered.

    An ANP problem q can be expressed as q<v, C>, where v = Ptime verification
    function, and C = certification dataset (description).

    [Note] Also testified by Church-Turing conjecture, no formal language can
           surpass the expressive power of a Turing machine (or algorithm, i.e.,
           the decisive operational process from parts to the whole). C
           language can be regarded as a high-level language of Turing machines,
           and as a formal language for knowledge or proof.

Prop1: ANP = ℕℙ
   Proof: ℕℙ ⊆ ANP and ANP ⊆ ℕℙ, therefore ANP=ℕℙ
          (The proof of the equivalence of ANP and the traditional
          Turing machine definition of ℕℙ is straightforward and lengthy, and
          not very important to most people. Although the definition of ANP does
          not depend on NDTM theory, there are thousands of real-world ℕℙℂ
          problems available for verification and reference)

Prop2: An ANP problem q<v,C> can be arbitrarily partitioned into two subproblems
       q1<v,C1>, q2<v,C2), where C = C1∪C2.
   Proof: The certification dataset can be recursively partitioned as follows:

          bool banp(Problem q) {
            if(certificate_size(q)<Thresh) { // Thresh is a small constant
              return solve_thresh_case(q); // Solve q in constant time
            }
            Problem q1,q2;
            split_certificate(q,q1,q2); // Split the certification dataset C
                                        // to form q1,q2, in which the number of
                                        // certificates are roughly the same.
            return banp(q1) || banp(q2); // Compute the subproblems respectively
          }

Prop3: Any two ANP problems q1 and q2 can be synthesized into another ANP
       problem q, denoted as q = q1 ⊕ q2. The certification dataset C and the
       verification function v of q are defined as follows:

       C = C1 ∪ C2     // C1 and C2 are the certification datasets of q1 and q2
                       // respectively

       bool v(x) {
         return v1(x) || v2(x);  // v1 and v2 are the verification functions of
                                 // q1 and q2 respectively
       }

       Therefore, we have the identity: q1<v1,C1>⊕ q2<v2,C2> = q<v1||v2, C1∪C2>.

Prop4: ℙ=ℕℙ iff the algorithm fnp in the ℕℙ definition (or ℕℙℂ algorithm) can be
       replaced by a Ptime algorithm.
   Proof: Omitted (A very direct semantic of 'equivalence')

Prop5: For ℕℙℂ subproblems q1<v,C1> and q2<v,C2> (same v), if C1 ∩ C2 = ∅, then
       there is no information in problem q1 that is sufficient in terms of
       order of complexity to speed up the computation of q2.
   Proof: Since ℕℙℂ is the most complex class of ℕℙ problems, by the definition
       of ANP, the order of card(C) of the ℕℙℂ problem must be of order O(2^|q|)
       no lower (any lower, ANP/ℕℙ problem cannot be completely reduced).
       We can add an AuxInfo object called 'auxiliary information' to banp to
       store the results after calculating a certain ℕℙℂ problem q, and rewrite
       it as banp2. Depending on the content of the auxiliary information,
       banp2 can represent possible algorithms for ANP/ℕℙℂ problems with
       complexities ranging from O(N) to O(2^N).

        bool banp2(Problem q, AuxInfo* ibuf) { // Calculate q and write the
                                      // obtained auxiliary information to *ibuf
        // Check and initialize *ibuf
        if(certificate_size(q)<Thresh) {
          return solve_thresh_case(q,ibuf);
        }
        Problem q1,q2;
        split_certificate(q,q1,q2);// q can only be reduced to ℕℙℂ subproblems
                                   // q1 and q2.
                                   // card(C1) and card(C2) are roughly equal.
        AuxInfo I;               // I stores information to help solve problems.
        if(banp2(q1,&I)==true) { // banp2(q1,I) recursively computes subproblem
                                 // q1 and stores any auxiliary information
                                 // that can be derived from q1 into I.
          write_ibuf1(ibuf,q);   // Write auxiliary information
          return true;           // The information obtained from subproblem q1
                                 // is valid for any problem q.
        }
        bool rv=banp2_i(q2,&I);  // Solve q2 with given information I of which
                                 // any source is effective for q2.
        write_ibuf2(ibuf,q);
        return rv;
      }

      [Note] From banp2(q1,&I), we know that the auxiliary information I is only
             meaningful if it contains information related to the certification
             dataset C1 of problem q1. This is because if it is not related, the
             computation of other subproblems can generate the auxiliary
             information by itself.

      The above `banp2_i` does not care which ANP problem (including trivial
      problems) the given information `I` originates from. The `I` generated can
      also provide auxiliary information for almost all other ANP problems.

      Since the auxiliary information I obtained from computing a fixed
      subproblem (including trivial problem) cannot provide sufficient
      information to accelerate computation to the extent of improving the
      complexity order for any other subproblem (would require infinite space/
      time), the proposition is thus proved (this proof also demonstrates that
      the complexity of the ℕℙℂ problem is O(2^N)).

Conclusion: According to Proposition 5, the certification data for the ℕℙℂ
      problem are basically independent and must be tested one by one. Since the
      ℕℙℂ problem has O(^|q|) certification data, the complexity of the ℕℙℂ
      problem is O(2^N), therefore ℙ≠ℕℙ.
-------------------------------------------------------------------------------

[toc] | [prev] | [next] | [standalone]

#123145

The claim is changed to "NPC is O(2^N)" which is stronger than "P!=NP".
The idea of reduction is removed.

The following is form
https://sourceforge.net/projects/cscall/files/MisFiles/PNP-proof-en.txt/download

-----------------------------------------------------------------------------
Algorithmic Problem::= A computer problem in which the computational steps are a
    function of the problem statement's length (size). This problem can be
    described asymptotically as the relationship between the problem size and
    the computational steps.
         
Polynomial-time procedure (or Ptime procedure)::= O(P) number of consecutive,
    fixed-sized basic operations (because the procedure is a deterministic
    process, it is sometimes called a "function" or "operation"). Therefore, as
    defined by O(P), O(P) number of Ptime procedures executed consecutively can
    also be considered as a single Ptime procedure.

ANP::= {q| q is a statement of a decision problem that a computer can solve in
    O(2^|q|) steps using the following fnp algorithmic template. q contains a
    certification dataset C, card(C)<=O(2^|q|), and a Ptime verification
    function v:C->{true,false}. If ∃c,v(c)=true, then the answer to problem q is
    true; otherwise, it is false.}
            
    // begin_certificate is a Ptime function that retrieves the first
    // Certificate element from the problem statement q. If this element does
    // not exist, it returns a unique and virtual EndC element.
    Certificate begin_certificate(Problem q);
     
    // end_certificate is a Ptime function that retrieves the element EndC from
    // the problem statement q.
    Certificate end_certificate(Problem q);
     
    // next_certificate is a Ptime function that retrieves the next element of
    // c from the certification dataset C. If this element does not exist,
    // return the EndC element.
    Certificate next_certificate(Problem q, Certificate c);
     
    // v is a Ptime function. v(c)==true if c is the element expected by the
    // problem.
    bool v(Certificate c);
 
    bool fnp(Problem q) {
      Certificate c, begin, end;   // Declare the certification data variable
      begin= begin_certificate(q); // begin is the first certification data
      end= end_certificate(q);     // end is the false data EndC used to
                                   // indicate the end.
      for(c = begin; c != end;
          c = next_certificate(q, c)) { // At most O(2^|q|) steps.
                                        // next_certificate(c) is a Ptime
                                        // function to get the next
                                        // certification data of c
          if(v(c) == true) return true; // v: C->{true, false} is a polynomial
                                        // time verification function.
      }
      return false;
    }

    Since a continuous O(P) number of Ptime functions (or instructions) can be
    combined into a single Ptime function, at roughly this complexity analysis,
    any Ptime function can be added, deleted, merged/split in the algorithm
    steps without affecting the algorithm's complexity. Perhaps in the end, only
    the number of decision branches needs to be considered.

    An ANP problem q can be expressed as q<v, C>, where v = Ptime verification
    function, and C = certification dataset (description).

    [Note] Also testified by Church-Turing conjecture: No formal language can
           surpass the expressive power of a Turing machine (or algorithm, i.e.,
           the decisive operational process from parts to the whole). C language
           can be regarded as a high-level language of Turing machines, and as
           a formal language for knowledge or proof.

Prop1: ANP = ℕℙ
   Proof: ℕℙ ⊆ ANP and ANP ⊆ ℕℙ, therefore ANP=ℕℙ
          (The proof of the equivalence of ANP and the traditional
          Turing machine definition of ℕℙ is straightforward and lengthy, and
          not very important to most people. Although the definition of ANP does
          not depend on NDTM theory, there are thousands of real-world ℕℙℂ
          problems available for verification and reference)

Prop2: An ANP problem q<v,C> can be arbitrarily partitioned into two subproblems
       q1<v,C1>, q2<v,C2), where C = C1∪C2.
   Proof: The certification dataset can be recursively partitioned as follows:

          bool banp(Problem q) {
            if(certificate_size(q)<Thresh) { // Thresh is a small constant
              return solve_thresh_case(q); // Solve q in constant time
            }
            Problem q1,q2;
            split_certificate(q,q1,q2); // Split the certification dataset C
                                        // to form q1,q2, in which the number of
                                        // certificates are roughly the same.
            return banp(q1) || banp(q2); // Compute the subproblems respectively
          }

Prop3: Any two ANP problems q1 and q2 can be synthesized into another ANP
       problem q, denoted as q = q1 ⊕ q2. The certification dataset C and the
       verification function v of q are defined as follows:

       C = C1 ∪ C2     // C1 and C2 are the certification datasets of q1 and q2
                       // respectively

       bool v(x) {
         return v1(x) || v2(x);  // v1 and v2 are the verification functions of
                                 // q1 and q2 respectively
       }

       Therefore, we have the identity: q1<v1,C1>⊕ q2<v2,C2> = q<v1||v2, C1∪C2>
       (The algebraic operation rules for '⊕'  are the same as those for
        addition in arithmetic).

Prop4: ℙ=ℕℙ iff the algorithm fnp in the ℕℙ definition (or ℕℙℂ algorithm) can be
       replaced by a Ptime algorithm.
   Proof: Omitted (A very direct semantic of 'equivalence')

Prop5: For ℕℙℂ subproblems q1<v,C1> and q2<v,C2> (same v, but not required), if
       C1 ∩ C2 = ∅, then there is no information in problem q1 that is
       sufficient in terms of order of complexity to speed up the computation
       of q2. I.e. the certification data of the ℕℙℂ problem are each, in the
       sense of computation, equivalently independent.
   Proof: Since ℕℙℂ is the most complex class of ℕℙ problems, by the definition
       of ANP, the order of card(C) of the ℕℙℂ problem must be of order O(2^|q|)
       ,no lower.
       We can add an AuxInfo object called 'auxiliary information' to banp to
       store the results after calculating a certain ℕℙℂ problem q, and rewrite
       it as banp2.
       Depending on the content of the auxiliary information, banp2 can
       represent possible algorithms for ANP/ℕℙℂ problems with complexities
       ranging from O(N) to O(2^N).

        bool banp2(Problem q, AuxInfo* ibuf) { // Calculate q and write the
                                      // obtained auxiliary information to *ibuf
        // Check and initialize *ibuf
        if(certificate_size(q)<Thresh) {
          return solve_thresh_case(q,ibuf);
        }
        Problem q1,q2;
        split_certificate(q,q1,q2);// The split function only requres Ptime
                                  // conversion from q to ℕℙℂ subproblems q1,q2,
                                  // others are non-issue.
        AuxInfo I;               // I stores information to help solve problems.
        if(banp2(q1,&I)==true) { // banp2(q1,I) recursively computes subproblem
                                 // q1 and stores any auxiliary information
                                 // that can be derived from q1 into I.
          write_ibuf1(ibuf,q);   // Write auxiliary information
          return true;           // The information obtained from subproblem q1
                                 // is useful? for any problem q.
        }
        bool rv=banp2_i(q2,&I);  // Solve q2 with given information I of which
                                 // any source is effective? for q2.
        write_ibuf2(ibuf,q);
        return rv;
      }

      [Note] From banp2(q1,&I), we know that the auxiliary information I is only
             meaningful to store information related to the certification
             dataset C1 of problem q1. This is because if it is not related, the
             computation of other subproblem can generate the auxiliary
             information by itself.

      The above `banp2_i` does not care which ℕℙℂ subproblem (including trivial
      problems) the given information `I` originates from. The `I` generated can
      also provide auxiliary information for almost all other ANP problems.

      Since the auxiliary information I obtained from computing a fixed
      subproblem (including trivial problem) cannot provide sufficient
      information to accelerate computation to the extent of improving the
      complexity order for any other subproblem (would require infinite space/
      time), the proposition is thus proved.

Conclusion: By Proposition 5, each certification data of the ℕℙℂ problem are
      independent in the sense of Ptime verification, the computation is
      equivalent to testing them one by one. Since the ℕℙℂ problem has O(^|q|)
      independent certification data, the complexity of the ℕℙℂ problem is
      O(2^N) (ℙ≠ℕℙ is proved in the way).
-----------------------------------------------------------------------------

[toc] | [prev] | [standalone]

Back to top | Article view | comp.lang.c++

csiph-web