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

Groups > comp.lang.c > #394233

P!=NP proof (using C/C++) for review

Show all headers | View raw

This file is intended a proof of ℙ≠ℕℙ. The contents may be updated anytime.
https://sourceforge.net/projects/cscall/files/MisFiles/PNP-proof-en.txt/download

The text is converted by google translate with modest modification from
https://sourceforge.net/projects/cscall/files/MisFiles/PNP-proof-zh.txt/download
Reader might want to try different translator or different settings.

-----------------------------------------------------------------------------
Algorithmic Problem::= A computer problem in which the number of computational
    steps is a function of the problem size. This problem can be described
    asymptotically between the size of the problem and the number of
    computational steps.

Polynomial-time program (or Ptime program)::= An algorithmic program (because a
    program is a deterministic process, it is sometimes called a "function",
    "operation," or "operation") that has O(P) consecutive, fixed steps.
    Therefore, by the O(P) definition, a Ptime program with O(P) consecutive
    steps can be considered a single Ptime program.

Reduction::= Computational problem A (the algorithm) can be converted into
    computational problem B by Ptime program, denoted as A≤B (because Ptime
    conversion itself includes computational problem A, any Ptime problem can
    be reduced to each other).

ℕℙ::= {q| q is a statement decision problem that can be solved by a computer in
    O(2^|q|) steps using the following np algorithm template. q contains the
    statement of set of Certificate C and the Ptime verification function
    v:C->{true, false}. If ∃c,v(c)=true, then the answer to the problem is true,
    and vice versa.}

    Because the values of c1size, c2size, ..., cnsize in the following C
    language algorithm template are dynamically derived from the description of
    problem q. Strictly, they are equivalent templates, the actual pattern may
    differ somehow.

    // get_certificate is a Ptime function.
    // Extracts the Certificate element corresponding to the function argument
    // from problem statement q.
    Certificate get_certificate(Problem q, Int idx1, Int idx2,...,Int idxn);

    Int c1size = The number obtained from problem q
    Int c2size = Same as above
    ...
    Int cnsize = Same as above

    bool np(Problem q) {
      for(Int idx1 = 0; idx1 < c1size; ++idx1) // n chained for loops
      for(Int idx2 = 0; idx2 < c2size; ++idx2)
      ...
      for(Int idxn = 0; idxn < cnsize; ++idxn) {
      Certificate c = get_certificate(q, idx1, idx2,..., idxn);
        if(v(c)==true) return true;
      }
      return false;
    }

    [Note] This definition of ℕℙ is equivalent to the traditional Turing machine
           definition of ℕℙ. The details of this proof are a bit lengthy and not
           very meaningful to most people, so I'll omit them.

    [Note] According to the Church-Turing Conjecture, no formal language can
           surpass the expressive power of a Turing machine. C can be considered
           a high-level language or "specification" of a Turing machine.

Prop 1: Since a consecutive O(P) number of Ptime functions (or instructions) can
    be combined into a single Ptime function, the above np algorithm is
    equivalent to the following np1 algorithm with a single for loop:

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

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

    // next_certificate is a Ptime function.
    // Extract the element after c from 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 iff c is the element expected by the
    // problem.
    bool v(Certificate c);

    bool np1(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|) loops. next_certificate(c)
                                  // Ptime function for finding the next
                                  // verification data for c
        if(v(c)==true) return true; // v:C->{true,false} is a polynomial time
                                    // verification function,
      }
      return false;
    }

Prop 2: ℕℙ problems can always be split into two sub-problems.
  Proof: The verification data set can be split into two and processed
         recursively 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); // Divide the verification data set C in q
                                  // into two sub-problems of size q1 and q2
                                  // approximately abs(|q1|-|q2|<=O(1))
      return banp(q1) || banp(q2); // Compute the sub-problems separately
    }

Prop 3: Any two ℕℙ problems q1 and q2 can be combined into another ℕℙ problem q,
    which can be expressed as q=q1⊕ q2. The verification data set C and
    verification function v for q are defined as follows:

    C = C1||C2   // C1, C2 are the verification data sets for q1 and q2,
                 // respectively

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

Prop 4: The banp(..) in Prop 2 above can add an object I (defined as a general
    form that stores information about how to accelerate the computation of a
    problem to Ptime after completing the computation of a problem):

    bool banp2(Problem q) {
      if(certificate_size(q)<Thresh) {
        return solve_thresh_case(q);
      }
      Problem q1,q2;
      split_certificate(q,q1,q2);
      Info I; // I stores information about accelerating the computation of the
              // problem
      if(banp_i(q1,&I)==true) { // banp_i(q1,I) computes banp(q1) and
                                // simultaneously stores any useful information
                                // that can be derived from q1 into I.
        return true;
      }
      return solv_remain(q2,I); // Solve the remaining problem q2 given the
                                // information in I.
    }

Prop 5: ℙ≠ℕℙ
    Proof: From banp2, we can see that if the solution to a ℕℙ subproblem always
    provides I information that accelerates the computation of other subproblems
    ,then due to the splitting and combining properties of the ℕℙ problem, The I
    from a fixed-type problem of trivial problems is also valid for
    solve_remain(q2,I). In other words, I is effetively ineffective. Therefore,
    no information I exists that can accelerate banp2 to Ptime.

    For example, from q, we can construct q' of the same size and with a Ptime
    algorithm. banp2(q⊕ q') can always obtain I information at Ptime that is not
    strongly correlated with q but can accelerate the computation of q by Ptime.
    This is impossible.

    The complexity of the banp (equivalent to np) algorithm is O(2^N).
    No algorithm exists that can accelerate the computation to Ptime, so ℙ≠ℕℙ.

+------------+
| References |
+------------+
 [1] THEORY OF COMPUTATION [Deric Wood]
 [2] ALGORITHMICS, Theory and Practice [Gilles Brassard, Paul Bratley]
 [3] AN INTRODUCTION TO FORMAL LANGUAGES AND AUTOMATA [Peter Linz]
 [4] https://sourceforge.net/projects/cscall/files/MisFiles/Computation-en.txt/download
    (Computing concepts and term definition)
-----------------------------------------------------------------------------

Back to comp.lang.c | Previous | Next | Find similar

Thread

P!=NP proof (using C/C++) for review wij <wyniijj5@gmail.com> - 2025-08-27 11:27 +0800

csiph-web