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

Groups > comp.theory > #105707 > unrolled thread

Improved ℙ≠ℕℙ proof

Back to article view | Back to comp.theory

Contents

  Improved ℙ≠ℕℙ proof wij <wyniijj5@gmail.com> - 2024-05-30 08:24 +0800
    Re: Improved ℙ≠ℕℙ proof wij <wyniijj5@gmail.com> - 2024-05-31 23:07 +0800
      Re: Improved ℙ≠ℕℙ proof immibis <news@immibis.com> - 2024-05-31 19:50 +0200
        Re: Improved ℙ≠ℕℙ proof wij <wyniijj5@gmail.com> - 2024-06-01 06:33 +0800
          Re: Improved ℙ≠ℕℙ proof immibis <news@immibis.com> - 2024-06-01 14:47 +0200
            Re: Improved ℙ≠ℕℙ proof wij <wyniijj5@gmail.com> - 2024-06-02 06:18 +0800
      Re: Improved ℙ≠ℕℙ proof wij <wyniijj5@gmail.com> - 2024-06-03 22:22 +0800
        Re: Improved ℙ≠ℕℙ proof wij <wyniijj5@gmail.com> - 2024-06-03 23:04 +0800
          Re: Improved ℙ≠ℕℙ proof wij <wyniijj5@gmail.com> - 2024-06-06 12:45 +0800
        Re: Improved ℙ≠ℕℙ proof immibis <news@immibis.com> - 2024-06-04 16:14 +0200
          Re: Improved ℙ≠ℕℙ proof wij <wyniijj5@gmail.com> - 2024-06-05 15:33 +0800

#105707 — Improved ℙ≠ℕℙ proof

This proof is quite direct and may be too easy to many. But proof is proof
The good thing is that this proof suggests a general method for problem complexity,
easy to (false) verify by reviewers. Any comments?

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

This proof suggests a general algorithm for problem complexity, easy to false
prove. With lots of algorithms out there, I only know a few of them, thus,
cannot effectively verify the proof. And, the details of this proof are many
and basic, concise description should be sufficient.

-----------------------------------------------------------------------------
Algorithmic problem::= Problems that can 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 within 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(n):

   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 interchangable. 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(n) includes nested loops for
         sets like C=C1×C2×C3×...

Theorem: Sequential execution of O(P) number of Ptime functions is equivalent to
        the execution of one single Ptime function.

Lemma1: If ANP=ℙ, then there exists a Ptime recursive algorithm (which normally
        contains only one recursive call) equivalent to temp_anp(..).
   Proof: The number of certificate data to infer in temp_anp(..) is O(2^|q|).
        If ANP=ℙ, then there exists an Ptime algorithm which only need to
        actually executes O(P) number of verification v(c) and performs the
        equivalent function of what the O(2^|q|) loop does. IOW, each execution
        of the v(c) can in average reduce O(2^N) uncertainties....This is
        equivalent to say that one Ptime computation can reduce the problem size
        (normally by 1). Then, what the smaller size problem left can be solved
        by a recursive call.

Lemma2: Assuming an ANP problem q is analysized by a recursive method and a
        recursive call has completed its task of solving the subproblem (of
        size= |q|-1). If the workload of what is left can be described as
        solving a subproblem, then, problem q can only be solved in O(2^N) steps
        , i.e. q∉ℙ.
   Proof: If the workload of what is left (denoted as W(|R|) from removing the
        assumingly solved subproblem is equivalent to the workload of solving R
        as a recursive subproblem, then, the workload of problem q is determined
        as (assume m1=|q|-1) O(2^m1)+O(2^m1)= O(2^|q|), regardless of 'possibly
        other algorithm' because the workloads are all the same described as
        solving a recursive subproblem.
        If the workload of what is left (i.e. R) is not equivalent to the
        workload of solving R as another subproblem, the workload of R must be
        less than O(2^N) steps (otherwise, it msut be solvable as a subproblem).
        Therefore, the workload of problem q is W(|q|)= W(|q-1|)+W(|R|)
        = |q|*W(|R|), a value less than O(2^N).

        Take Subset Sum as example:
        bool subset_sum(const UInt* set, UInt n_elem, UInt sum) {
          if(sum==0) return true;
          if(n_elem==0) return false;

          if(set[n_elem-1]>sum) {
            return subset_sum(set,n_elem-1,sum);
          }
          return subset_sum(set,n_elem-1,sum) ||  // Subproblem that does not
                                                  // contain the last element.
                 subset_sum(set,n_elem-1,sum- set[n_elem-1]);
        }

        Assuming a subproblem case of subset_sum is completed, the left task is
        equivalent to solving another subbproblem. Therefore, Subset Sum∉ℙ.

Several ℕℙℂ instances that are easy to test by Lemma2, e.g. TSP,... can also be
easily deduced only solvable in O(2^N) steps, i.e. ℕℙℂ≠ℙ. Thus, we can conclude
ℙ≠ℕℙ.
-----------------------------------------------------------------------------

[toc] | [next] | [standalone]

#105823

Woo, the updated proof is even lots shorter (and intuitive?).
-----------------------------------------------------------------------------


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(n):

   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(n) 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
          }

The proof above also illustrates that ANP is merely a kind of class of problems
that temp_anp can handle independent certificates. I.e. the result of v(c1) and
v(c2) may be completely unrelated. As there are n number of such certificates,
at most such n number of steps are required. This conclusion applies to any
number of n (this view can also be formed by the definition of temp_anp, the
proof just provides another view in subproblems).

Because there are O(2^N) certificates, ANP≠ℙ. If ANP⊆ℕℙ, ℙ≠ℕℙ can be concluded.
-----------------------------------------------------------------------------

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

#105832

On 31/05/24 17:07, wij wrote:
> This file is intended a proof that ℙ≠ℕℙ. The contents may be updated anytime.

But you can't prove that this is the fastest way to solve the problem.

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

#105844

On Fri, 2024-05-31 at 19:50 +0200, immibis wrote:
> On 31/05/24 17:07, wij wrote:
> > This file is intended a proof that ℙ≠ℕℙ. The contents may be updated anytime.
> 
> But you can't prove that this is the fastest way to solve the problem.
> 
   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;
   }

The definition already says the loop is iterated O(2^N) times for certificate.
Such thing is categorized as 'intuition' which do not need to prove.

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

#105867

On 1/06/24 00:33, wij wrote:
> On Fri, 2024-05-31 at 19:50 +0200, immibis wrote:
>> On 31/05/24 17:07, wij wrote:
>>> This file is intended a proof that ℙ≠ℕℙ. The contents may be updated anytime.
>>
>> But you can't prove that this is the fastest way to solve the problem.
>>
>     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;
>     }
> 
> The definition already says the loop is iterated O(2^N) times for certificate.
> Such thing is categorized as 'intuition' which do not need to prove.
> 
> 

But there could be a faster way to find the certificate.

Example:

bool v(unbounded_integer c) {return c*c == 40000;}

You could use 201 iterations to find that v(200) is true, and that would 
be O(2^N) with N being the problem length. But you could also look 
inside the function v, and see that the problem is calculating the 
square root of a certain number, and then you could calculate the square 
root of that number. The problem is in NP, but it's also in P because 
there's a faster solution. So you can't prove that problems aren't in P 
this way.

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

#105973

On Sat, 2024-06-01 at 14:47 +0200, immibis wrote:
> On 1/06/24 00:33, wij wrote:
> > On Fri, 2024-05-31 at 19:50 +0200, immibis wrote:
> > > On 31/05/24 17:07, wij wrote:
> > > > This file is intended a proof that ℙ≠ℕℙ. The contents may be updated anytime.
> > > 
> > > But you can't prove that this is the fastest way to solve the problem.
> > > 
> >     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;
> >     }
> > 
> > The definition already says the loop is iterated O(2^N) times for certificate.
> > Such thing is categorized as 'intuition' which do not need to prove.
> > 
> > 
> 
> But there could be a faster way to find the certificate.
> 
> Example:
> 
> bool v(unbounded_integer c) {return c*c == 40000;}
> 
> You could use 201 iterations to find that v(200) is true, and that would 
> be O(2^N) with N being the problem length. But you could also look 
> inside the function v, and see that the problem is calculating the 
> square root of a certain number, and then you could calculate the square 
> root of that number. The problem is in NP, but it's also in P because 
> there's a faster solution. So you can't prove that problems aren't in P 
> this way.

"...More precisely, ANP is the set of problems that can be solved by the
   following pseudo-C/C++ program temp_anp(q):..."

All that temp_anp(..) can solve are ANP problems, including a specific subset 
of O(2^N) problems.

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

#106141

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

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

#106148

On Mon, 2024-06-03 at 22:22 +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, ℙ≠ℕℙ.

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

#106377

On Mon, 2024-06-03 at 23:04 +0800, wij wrote:


ℙ≠ℕℙ Proved. https://sourceforge.net/projects/cscall/files/MisFiles/PNP-proof-en.txt/download
...[cut]
    Note: Another super short proof that ℙ≠ℕℙ (might be less constructive).
    Proof: If ℙ=ℕℙ, then ℕℙℂ=ℙ. All the problems in ℕℙ are Ptime reduciable.
           That means all the proofs that prove "Decide whether or not a given
           number is even" is not a ℕℙℂ are false proofs. Since such proofs are
           considered valid, ℕℙℂ and ℙ is not the same, therefore, ℙ≠ℕℙ.

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

#106237

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.

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

#106294

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.

[toc] | [prev] | [standalone]

Back to top | Article view | comp.theory

csiph-web