Path: ...!feeds.phibee-telecom.net!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.theory
Subject: Re: Improved =?UTF-8?Q?=E2=84=99=E2=89=A0=E2=84=95=E2=84=99?= proof
Date: Mon, 03 Jun 2024 23:04:09 +0800
Organization: A noiseless patient Spider
Lines: 136
Message-ID: <8cfbbf143df2be693e8a4ca79c9c7376cf086741.camel@gmail.com>
References: <108d3c553ccae9c7e6eeb1b8b1a85a52b8b0b78d.camel@gmail.com>
	 <eed8bcaeee2337a7d842401b4bd6e2e409ddc213.camel@gmail.com>
	 <9bf939d70b9ee022a01a7b1dd9eaa705da397d88.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 17:04:11 +0200 (CEST)
Injection-Info: dont-email.me; posting-host="53ecd3a08a774183dc348db4349cad0c";
	logging-data="4135847"; mail-complaints-to="abuse@eternal-september.org";	posting-account="U2FsdGVkX19JOySd8E082NZWFMjurM9n"
User-Agent: Evolution 3.50.2 (3.50.2-1.fc39)
Cancel-Lock: sha1:hP9h4LxgnhIvh0secMFpCtf/PnY=
In-Reply-To: <9bf939d70b9ee022a01a7b1dd9eaa705da397d88.camel@gmail.com>
Bytes: 7776

On Mon, 2024-06-03 at 22:22 +0800, wij wrote:
> The P!=3DNP proof should be completed.
> The updated proof may even be shorter, intuitive and robust !!!
> ---------------------------------------------------------------
>=20
>=20
> This file is intended a proof that =E2=84=99=E2=89=A0=E2=84=95=E2=84=99. =
The contents may be updated anytime.
> https://sourceforge.net/projects/cscall/files/MisFiles/PNP-proof-en.txt/d=
ownload
>=20
> -------------------------------------------------------------------------=
----
> Algorithmic problem::=3D Problems that can be processed by asymptotic ana=
lysis.
>=20
> ANP::=3D Another NP is a set defined as {q| q is a description of the alg=
orithmic
> =C2=A0=C2=A0 decision problem that provides 1. A set of certificate data =
C 2. A Ptime
> =C2=A0=C2=A0 (Polynomial time) verification method v 3. The answer of q i=
s 'yes' iff
> =C2=A0=C2=A0 there exists a certificate c, c=E2=88=88C, such that v(c) is=
 true 4. q can be
> =C2=A0=C2=A0 computed in at most O(2^|q|) steps. }.
> =C2=A0=C2=A0 More precisely, ANP is the set of problems that can be solve=
d by the=20
> =C2=A0=C2=A0 following pseudo-C/C++ program temp_anp(q):
>=20
> =C2=A0=C2=A0 bool temp_anp(Problem q) {=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=
=A0=C2=A0=C2=A0=C2=A0=C2=A0 // Problem: Description of the problem
> =C2=A0=C2=A0=C2=A0=C2=A0 Certificate c,begin,end;=C2=A0=C2=A0=C2=A0=C2=A0=
=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0 // Certificate data can be accessed by
> =C2=A0=C2=A0=C2=A0=C2=A0 begin=3D get_begin_certificate(q);=C2=A0=C2=A0 /=
/=C2=A0=C2=A0 iteration, at least.
> =C2=A0=C2=A0=C2=A0=C2=A0 end=C2=A0 =3D get_end_certificate(q);
> =C2=A0=C2=A0=C2=A0=C2=A0 for(c=3Dbegin; c!=3Dend; c=3Dnext(c)) {=C2=A0 //=
 O(2^|n|) loop (see Note2)
> =C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0 if(v(c)) return true;=C2=A0=C2=A0=C2=
=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0 // v:Certificate->{true=
,false}, Ptime
> =C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=
=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=
=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=
=C2=A0=C2=A0 //=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0 verification function.
> =C2=A0=C2=A0=C2=A0=C2=A0 }
> =C2=A0=C2=A0=C2=A0=C2=A0 return false;
> =C2=A0=C2=A0 }
>=20
> =C2=A0=C2=A0 Note1: Relative to the Turing Machine language for =E2=84=95=
=E2=84=99, the reason using
> =C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0 pseudo-C/C++ is that 1.C=
-code (almost all high level programming
> =C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0 language not involving s=
pecial hardware features) and TM language are
> =C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0 computationally intercha=
ngeable. 2.It describes the problem more
> =C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0 clearly (but not always)=
 3.The result 'false' is visible 4. =E2=84=95=E2=84=99
> =C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0 definition does not say =
the certificate C and the verication v are
> =C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0 given, fixed arguments. =
In ANP, v(c) is explicitly spedified a Ptime
> =C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0 function 5.Easier for ma=
chine aided verification.
>=20
> =C2=A0=C2=A0 Note2: The semantics of the for loop in temp_anp(q) includes=
 nested loops for
> =C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0 sets like C=3DC1=C3=97C2=
=C3=97C3=C3=97...
>=20
> Polynomial time procedure::=3D (or polynomial time function) A procedure =
composed
> =C2=A0=C2=A0 of sequential execution of O(P) number of fixed-time procedu=
res.
> =C2=A0=C2=A0 (Therefore, O(P) number of sequential Ptime procedure is equ=
ivalent to a
> =C2=A0=C2=A0 single Ptime procedure)
>=20
> Size-1-subproblem::=3D The problem whose size of input is less by one tha=
n that
> =C2=A0=C2=A0 of the orginal problem.
>=20
> Theorem: ANP problem can be divided into two size-1-subproblems.
> =C2=A0=C2=A0 Proof: By spliting the certificate as follow:
> =C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0 bool temp_anp(Prob=
lem q) {
> =C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0 if(q.c=
ertificate().size()<Thresh) { // Thresh is a small constant
> =C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=
=C2=A0 return solve_thresh_case(q);
> =C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0 }
> =C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0 Proble=
m q1,q2;
> =C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0 split_=
certificate(q,q1,q2);=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0 // split th=
e certificate in q
> =C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0 return=
 temp_anp(q1) || temp_anp(q2); // to form q1,q2
> =C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0 }
>=20
> 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 =
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|)=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.
> -------------------------------------------------------------------------=
----

A typo in the last paragraph:


Assume solving some =E2=84=95=E2=84=99=E2=84=82 problem by temp_anp(q) whos=
e 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 the assumed Ptime. Therefore, =
=E2=84=99=E2=89=A0=E2=84=95=E2=84=99.