Re: Improved ℙ≠ℕℙ proof

On Tue, 2024-06-04 at 16:14 +0200, immibis wrote:

On 3/06/24 16:22, wij wrote:

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, ℙ≠ℕℙ.

 
If I understand it correctly, you think that if an algorithm for solving
a problem takes O(2^N) complexity then the problem can't be P-time.
 
But this is not correct. There are slow algorithms for fast problems.
For example, if I know a binary number M, and I want to calculate
whether all binary numbers with the same number of bits are less than or
equal to M, I could do it by looping through all the binary numbers with
the same number of bits, and checking if each one is less or equal. That
would be an O(2^N) algorithm. Or, I could think about the problem for a
bit, and then check whether all the bits in M are 1. That would be an
O(N) algorithm. Since there is an O(N) algorithm, it is a P-time problem
- even though an O(2^N) algorithm exists as well.

The proof was modified in more detail:
...
... See the link (same as above)
...
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 ℙ≠ℕℙ.
-----------------------------------------------------------------------------

If I understand your question correctly, if solv_remain(q2,I) can be computed
in Ptime ANYWAY, that will lead to say that any problem in ℕℙ can be Ptime
reduced to a dummy-fixed-time problem... that would be another 'humiliating'
proof. The proof above is more 'constructive' in that the method is resuable
(hopefully) to analyse other problems and conquer searching problems.