Path: ...!eternal-september.org!feeder3.eternal-september.org!news.eternal-september.org!.POSTED!not-for-mail
From: wij <wyniijj5@gmail.com>
Newsgroups: comp.theory
Subject: Re: Improved =?UTF-8?Q?=E2=84=99=E2=89=A0=E2=84=95=E2=84=99?= proof
Date: Fri, 31 May 2024 23:07:13 +0800
Organization: A noiseless patient Spider
Lines: 98
Message-ID: <eed8bcaeee2337a7d842401b4bd6e2e409ddc213.camel@gmail.com>
References: <108d3c553ccae9c7e6eeb1b8b1a85a52b8b0b78d.camel@gmail.com>
MIME-Version: 1.0
Content-Type: text/plain; charset="UTF-8"
Content-Transfer-Encoding: quoted-printable
Injection-Date: Fri, 31 May 2024 17:07:15 +0200 (CEST)
Injection-Info: dont-email.me; posting-host="58e01b5a2bbe399e2a0ce9c1509683fb";
	logging-data="2399439"; mail-complaints-to="abuse@eternal-september.org";	posting-account="U2FsdGVkX1/qN0Ujo3Je5qZgCEJGF2Ga"
User-Agent: Evolution 3.50.2 (3.50.2-1.fc39)
Cancel-Lock: sha1:EgJ7lhgYF5Vwqjl8AZFTTxVPhuA=
In-Reply-To: <108d3c553ccae9c7e6eeb1b8b1a85a52b8b0b78d.camel@gmail.com>
Bytes: 4970


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


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

---------------------------------------------------------------------------=
--
Algorithmic problem::=3D Problems that can be processed by asymptotic analy=
sis.

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=20
   computed in at most O(2^|q|) steps. }.
   More precisely, ANP is the set of problems that can be solved by the=20
   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 interchangeable. 2.It describes the problem more
         clearly (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 Pti=
me
         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...

Polynomial time procedure::=3D (or polynomial time function) A procedure co=
mposed
   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::=3D 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 consta=
nt
              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 prob=
lems
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 certificat=
es,
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, th=
e
proof just provides another view in subproblems).

Because there are O(2^N) certificates, ANP=E2=89=A0=E2=84=99. If ANP=E2=8A=
=86=E2=84=95=E2=84=99, =E2=84=99=E2=89=A0=E2=84=95=E2=84=99 can be conclude=
d.
---------------------------------------------------------------------------=
--