Path: ...!news.mixmin.net!eternal-september.org!feeder3.eternal-september.org!news.eternal-september.org!.POSTED!not-for-mail
From: wij <wyniijj5@gmail.com>
Newsgroups: comp.theory
Subject: Improved =?UTF-8?Q?=E2=84=99=E2=89=A0=E2=84=95=E2=84=99?= proof
Date: Thu, 30 May 2024 08:24:39 +0800
Organization: A noiseless patient Spider
Lines: 138
Message-ID: <108d3c553ccae9c7e6eeb1b8b1a85a52b8b0b78d.camel@gmail.com>
MIME-Version: 1.0
Content-Type: text/plain; charset="UTF-8"
Content-Transfer-Encoding: quoted-printable
Injection-Date: Thu, 30 May 2024 02:24:41 +0200 (CEST)
Injection-Info: dont-email.me; posting-host="3a99004b9bc66ea0fda76d3933d386d8";
	logging-data="1444060"; mail-complaints-to="abuse@eternal-september.org";	posting-account="U2FsdGVkX1/AiKRMp9vSVTZIRqbvDpZO"
User-Agent: Evolution 3.50.2 (3.50.2-1.fc39)
Cancel-Lock: sha1:CnKH2rCEbEf3rt4gTXHdKmOhi6Q=
Bytes: 6783

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 com=
plexity,
easy to (false) verify by reviewers. Any comments?

This file is intended a proof that =E2=84=99=E2=89=A0=E2=84=95=E2=84=99. Th=
e contents may be updated anytime.
https://sourceforge.net/projects/cscall/files/MisFiles/PNP-proof-en.txt/dow=
nload

This proof suggests a general algorithm for problem complexity, easy to fal=
se
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 man=
y
and basic, concise description should be sufficient.

---------------------------------------------------------------------------=
--
Algorithmic problem::=3D Problems that can processed by asymptotic analysis=
..

ANP::=3D Another NP is a set defined as {q| q is a description of the algor=
ithmic
   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=E2=88=88C, such that v(c) is true 4. q c=
an 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 prob=
lem
     Certificate c,begin,end;           // Certificate data can be accessed=
 by
     begin=3D get_begin_certificate(q);   //   iteration, at least.
     end  =3D get_end_certificate(q);
     for(c=3Dbegin; c!=3Dend; c=3Dnext(c)) {  // O(2^|n|) loop (see Note2)
       if(v(c)) return true;            // v:Certificate->{true,false}, Pti=
me
                                        //      verification function.
     }
     return false;
   }

   Note1: Relative to the Turing Machine language for =E2=84=95=E2=84=99, t=
he 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 cl=
early
         (but not always) 3.The result 'false' is visible 4. =E2=84=95=E2=
=84=99 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 loop=
s for
         sets like C=3DC1=C3=97C2=C3=97C3=C3=97...

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

Lemma1: If ANP=3D=E2=84=99, 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=3D=E2=84=99, 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 execu=
tion
        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 so=
lved
        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=3D |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=E2=88=89=E2=84=99.
   Proof: If the workload of what is left (denoted as W(|R|) from removing =
the
        assumingly solved subproblem is equivalent to the workload of solvi=
ng R
        as a recursive subproblem, then, the workload of problem q is deter=
mined
        as (assume m1=3D|q|-1) O(2^m1)+O(2^m1)=3D O(2^|q|), regardless of '=
possibly
        other algorithm' because the workloads are all the same described a=
s
        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 subprob=
lem).
        Therefore, the workload of problem q is W(|q|)=3D W(|q-1|)+W(|R|)
        =3D |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=3D=3D0) return true;
          if(n_elem=3D=3D0) 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 n=
ot
                                                  // contain the last eleme=
nt.
                 subset_sum(set,n_elem-1,sum- set[n_elem-1]);
        }

        Assuming a subproblem case of subset_sum is completed, the left tas=
k is
        equivalent to solving another subbproblem. Therefore, Subset Sum=E2=
=88=89=E2=84=99.

Several =E2=84=95=E2=84=99=E2=84=82 instances that are easy to test by Lemm=
a2, e.g. TSP,... can also be
easily deduced only solvable in O(2^N) steps, i.e. =E2=84=95=E2=84=99=E2=84=
=82=E2=89=A0=E2=84=99. Thus, we can conclude
=E2=84=99=E2=89=A0=E2=84=95=E2=84=99.
---------------------------------------------------------------------------=
--