Path: ...!news.misty.com!2.eu.feeder.erje.net!feeder.erje.net!eternal-september.org!feeder3.eternal-september.org!news.eternal-september.org!.POSTED!not-for-mail
From: wij <wyniijj5@gmail.com>
Newsgroups: comp.lang.c
Subject: Re: Improved =?UTF-8?Q?=E2=84=99=E2=89=A0=E2=84=95=E2=84=99?= proof
Date: Mon, 03 Jun 2024 22:26:53 +0800
Organization: A noiseless patient Spider
Lines: 95
Message-ID: <ec80bfdc7ee9ce8b143619f10c97eeb9d4ba6fe4.camel@gmail.com>
References: <933be7149a1cfdcd0abf2e7b793c20c8a00996ea.camel@gmail.com>
MIME-Version: 1.0
Content-Type: text/plain; charset="UTF-8"
Content-Transfer-Encoding: quoted-printable
Injection-Date: Mon, 03 Jun 2024 16:26:54 +0200 (CEST)
Injection-Info: dont-email.me; posting-host="53ecd3a08a774183dc348db4349cad0c";
	logging-data="4135847"; mail-complaints-to="abuse@eternal-september.org";	posting-account="U2FsdGVkX19uNgV+vLARVm1IfqyKGDLJ"
User-Agent: Evolution 3.50.2 (3.50.2-1.fc39)
Cancel-Lock: sha1:02BPCwV9aAqNsilMUUohAGqh5eA=
In-Reply-To: <933be7149a1cfdcd0abf2e7b793c20c8a00996ea.camel@gmail.com>
Bytes: 5114

The P!=3DNP proof should be completed.
The updated proof may even be shorter, intuitive and robust !!!
---------------------------------------------------------------


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

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

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 =E2=84=99=3D=E2=84=95=E2=84=99, which means the remaining task can be co=
mpleted independently in Ptime
without I. In this sitution, solve_remain(q2,I) is equivalent to temp_anp(q=
2).
But the complexity of computation is W(|q|)=3DW(|q|-1)+ W(|q|-1)=3D 2^(|q|-=
1)*W(1),
a O(2^N) level of complexity contradicting he assumed Ptime. Therefore, =E2=
=84=99=E2=89=A0=E2=84=95=E2=84=99.
---------------------------------------------------------------------------=
--