Forum: Too Lazy BBS

Who's Online

System Info

Sysop:	Amessyroom
Location:	Fayetteville, NC
Users:	23
Nodes:	6 (0 / 6)
Uptime:	52:08:46
Calls:	583
Files:	1,139
Messages:	111,532

P!=NP proof for review

From wij@wyniijj5@gmail.com to comp.theory on Wed Aug 27 11:51:36 2025

From Newsgroup: comp.theory

--=-cVPsilWlsvBLtJlfaYOi
Content-Type: text/plain; charset="UTF-8"
Content-Transfer-Encoding: quoted-printable

I just updated a P!=3DNP proof for review, comments, thanks.

------- =20
This file is intended a proof of =E2=84=99=E2=89=A0=E2=84=95=E2=84=99. The = contents may be updated anytime. =20 [https://sourceforge.net/projects/cscall/files/MisFiles/PNP-proof-en.txt/do= wnload](https://sourceforge.net/projects/cscall/files/MisFiles/PNP-proof-en= .txt/download)

The text is converted by google translate with modest modification from =
=20 [https://sourceforge.net/projects/cscall/files/MisFiles/PNP-proof-zh.txt/do= wnload](https://sourceforge.net/projects/cscall/files/MisFiles/PNP-proof-zh= .txt/download) =20
Reader might want to try different translator or different settings.

---------------------------------------------------------------------------=
-- =20
Algorithmic Problem::=3D A computer problem in which the number of computat= ional =20
steps is a function of the problem size. This problem can be described =20 asymptotically between the size of the problem and the number of =20 computational steps.

Polynomial-time program (or Ptime program)::=3D An algorithmic program (bec= ause a =20
program is a deterministic process, it is sometimes called a "function", =
=20
"operation," or "operation") that has O(P) consecutive, fixed steps. =20 Therefore, by the O(P) definition, a Ptime program with O(P) consecutive =
=20
steps can be considered a single Ptime program.

Reduction::=3D Computational problem A (the algorithm) can be converted int=
o =20
computational problem B by Ptime program, denoted as A=E2=89=A4B (because P= time =20
conversion itself includes computational problem A, any Ptime problem can =
=20
be reduced to each other).

=E2=84=95=E2=84=99::=3D {q| q is a statement decision problem that can be s= olved by a computer in =20
O(2^|q|) steps using the following np algorithm template. q contains the =
=20
statement of set of Certificate C and the Ptime verification function =20 v:C->{true, false}. If =E2=88=83c,v(c)=3Dtrue, then the answer to the probl=
em is true, =20
and vice versa.}

Because the values of c1size, c2size, ..., cnsize in the following C =20 language algorithm template are dynamically derived from the description of=
=20
problem q. Strictly, they are equivalent templates, the actual pattern may = =20
differ somehow.

// get_certificate is a Ptime function. =20
// Extracts the Certificate element corresponding to the function argument = =20
// from problem statement q. =20
Certificate get_certificate(Problem q, Int idx1, Int idx2,...,Int idxn);

Int c1size =3D The number obtained from problem q =20
Int c2size =3D Same as above =20
... =20
Int cnsize =3D Same as above

bool np(Problem q) { =20
for(Int idx1 =3D 0; idx1 < c1size; ++idx1) // n chained for loops =20
for(Int idx2 =3D 0; idx2 < c2size; ++idx2) =20
... =20
for(Int idxn =3D 0; idxn < cnsize; ++idxn) { =20
Certificate c =3D get_certificate(q, idx1, idx2,..., idxn); =20 if(v(c)=3D=3Dtrue) return true; =20
} =20
return false; =20
}

[Note] This definition of =E2=84=95=E2=84=99 is equivalent to the tradition=
al Turing machine =20
definition of =E2=84=95=E2=84=99. The details of this proof are a bit lengt=
hy and not =20
very meaningful to most people, so I'll omit them.

[Note] According to the Church-Turing Conjecture, no formal language can =
=20
surpass the expressive power of a Turing machine. C can be considered =20
a high-level language or "specification" of a Turing machine.

Prop 1: Since a consecutive O(P) number of Ptime functions (or instructions=
) can =20
be combined into a single Ptime function, the above np algorithm is =20 equivalent to the following np1 algorithm with a single for loop:

// begin_certificate is a Ptime function. =20
// Extract the first Certificate element from problem statement q. If this = =20
// element does not exist, return the unique and virtual EndC element. =20 Certificate begin_certificate(Problem q);

// end_certificate is a Ptime function. =20
// Extract the element EndC from problem statement q. =20
Certificate end_certificate(Problem q);

// next_certificate is a Ptime function. =20
// Extract the element after c from problem statement q. If this element =
=20
// does not exist, return the EndC element. =20
Certificate next_certificate(Problem q, Certificate c);

// v is a Ptime function. v(c)=3D=3Dtrue iff c is the element expected by t=
he =20
// problem. =20
bool v(Certificate c);

bool np1(Problem q) { =20
Certificate c, begin, end; // Declare the verification data variable =20
begin =3D begin_certificate(q); // begin is the first verification data =
=20
end =3D end_certificate(q); // end is the false data EndC used to indicate = =20
// the end =20
for(c=3Dbegin; c!=3Dend; =20
c=3Dnext_certificate(q,c)) {// At most O(2^|q|) loops. next_certificate(c) = =20
// Ptime function for finding the next =20
// verification data for c =20
if(v(c)=3D=3Dtrue) return true; // v:C->{true,false} is a polynomial time =
=20
// verification function, =20
} =20
return false; =20
}

Prop 2: =E2=84=95=E2=84=99 problems can always be split into two sub-proble= ms. =20
Proof: The verification data set can be split into two and processed =20 recursively as follows:

bool banp(Problem q) { =20
if(certificate_size(q)<Thresh) { // Thresh is a small constant =20
return solve_thresh_case(q); // Solve q in constant time =20
} =20
Problem q1,q2; =20
split_certificate(q,q1,q2); // Divide the verification data set C in q =20
// into two sub-problems of size q1 and q2 =20
// approximately abs(|q1|-|q2|<=3DO(1)) =20
return banp(q1) || banp(q2); // Compute the sub-problems separately =20
}

Prop 3: Any two =E2=84=95=E2=84=99 problems q1 and q2 can be combined into = another =E2=84=95=E2=84=99 problem q, =20
which can be expressed as q=3Dq1=E2=8A=95 q2. The verification data set C a=
nd =20
verification function v for q are defined as follows:

C =3D C1||C2 // C1, C2 are the verification data sets for q1 and q2, =20
// respectively

bool v(x) { =20
return v1(x) || v2(x); // v1, v2 are the verification functions for q1 =20
// and q2, respectively =20
}

Prop 4: The banp(..) in Prop 2 above can add an object I (defined as a gene= ral =20
form that stores information about how to accelerate the computation of a =
=20
problem to Ptime after completing the computation of a problem):

bool banp2(Problem q) { =20
if(certificate_size(q)<Thresh) { =20
return solve_thresh_case(q); =20
} =20
Problem q1,q2; =20
split_certificate(q,q1,q2); =20
Info I; // I stores information about accelerating the computation of the =
=20
// problem =20
if(banp_i(q1,&I)=3D=3Dtrue) { // banp_i(q1,I) computes banp(q1) and =20
// simultaneously stores any useful information =20
// that can be derived from q1 into I. =20
return true; =20
} =20
return solv_remain(q2,I); // Solve the remaining problem q2 given the =20
// information in I. =20
}

Prop 5: =E2=84=99=E2=89=A0=E2=84=95=E2=84=99 =20
Proof: From banp2, we can see that if the solution to a =E2=84=95=E2=84=99 = subproblem always =20
provides I information that accelerates the computation of other subproblem=
s =20
,then due to the splitting and combining properties of the =E2=84=95=E2=84=
=99 problem, The I =20
from a fixed-type problem of trivial problems is also valid for =20 solve_remain(q2,I). In other words, I is effetively ineffective. Therefore,=
=20
no information I exists that can accelerate banp2 to Ptime.

For example, from q, we can construct q' of the same size and with a Ptime = =20
algorithm. banp2(q=E2=8A=95 q') can always obtain I information at Ptime th=
at is not =20
strongly correlated with q but can accelerate the computation of q by Ptime=
. =20
This is impossible.

The complexity of the banp (equivalent to np) algorithm is O(2^N). =20
No algorithm exists that can accelerate the computation to Ptime, so =E2=84= =99=E2=89=A0=E2=84=95=E2=84=99.

+------------+ =20
| References | =20
+------------+ =20
[1] THEORY OF COMPUTATION [Deric Wood] =20
[2] ALGORITHMICS, Theory and Practice [Gilles Brassard, Paul Bratley] =20
[3] AN INTRODUCTION TO FORMAL LANGUAGES AND AUTOMATA [Peter Linz] =20
[4] [https://sourceforge.net/projects/cscall/files/MisFiles/Computation-en.= txt/download](https://sourceforge.net/projects/cscall/files/MisFiles/Comput= ation-en.txt/download) =20
(Computing concepts and term definition) =20 ---------------------------------------------------------------------------=
--

--=-cVPsilWlsvBLtJlfaYOi
Content-Type: text/html; charset="utf-8"
Content-Transfer-Encoding: quoted-printable

I just updated a P!=3DNP proof for review, comments, thanks.
<hr />
This file is intended a proof of =E2=84=99=E2=89=A0=E2=84=95=E2=84=99. T=
he contents may be updated anytime. 
<a href=3D"https://sourceforge.net/projects/cscall/files/MisFiles/PNP-proof= -en.txt/download">https://sourceforge.net/projects/cscall/files/MisFiles/PN= P-proof-en.txt/download</a>
The text is converted by google translate with modest modification from<=
br />
<a href=3D"https://sourceforge.net/projects/cscall/files/MisFiles/PNP-proof= -zh.txt/download">https://sourceforge.net/projects/cscall/files/MisFiles/PN= P-proof-zh.txt/download</a> 
Reader might want to try different translator or different settings.
<hr />
Algorithmic Problem::=3D A computer problem in which the number of compu= tational 
steps is a function of the problem size. This problem can be described computational steps.
Polynomial-time program (or Ptime program)::=3D An algorithmic program (= because a 
program is a deterministic process, it is sometimes called a "function= ", 
"operation," or "operation") that has O(P) consecutive,=
fixed steps. 
Therefore, by the O(P) definition, a Ptime program with O(P) consecutive<br=

steps can be considered a single Ptime program.
Reduction::=3D Computational problem A (the algorithm) can be converted = into 
computational problem B by Ptime program, denoted as A=E2=89=A4B (because P= time 
conversion itself includes computational problem A, any Ptime problem can<b=
r />
be reduced to each other).
=E2=84=95=E2=84=99::=3D {q| q is a statement decision problem that can b=
e solved by a computer in 
O(2^|q|) steps using the following np algorithm template. q contains the<br=

statement of set of Certificate C and the Ptime verification function v:C->{true, false}. If =E2=88=83c,v(c)=3Dtrue, then the answer to the pr= oblem is true, 
and vice versa.}
Because the values of c1size, c2size, ..., cnsize in the following C 
problem q. Strictly, they are equivalent templates, the actual pattern may<=
br />
differ somehow.
// get_certificate is a Ptime function. 
// Extracts the Certificate element corresponding to the function argument<=
br />
// from problem statement q. 
Certificate get_certificate(Problem q, Int idx1, Int idx2,...,Int idxn);</p=

Int c1size =3D The number obtained from problem q 
Int c2size =3D Same as above 
... 
Int cnsize =3D Same as above
bool np(Problem q) { 
for(Int idx1 =3D 0; idx1 < c1size; ++idx1) // n chained for loops for(Int idx2 =3D 0; idx2 < c2size; ++idx2) 
... 
for(Int idxn =3D 0; idxn < cnsize; ++idxn) { 
Certificate c =3D get_certificate(q, idx1, idx2,..., idxn); if(v(c)=3D=3Dtrue) return true; 
} 
return false; 
}
[Note] This definition of =E2=84=95=E2=84=99 is equivalent to the tradit= ional Turing machine 
definition of =E2=84=95=E2=84=99. The details of this proof are a bit lengt=
hy and not 
very meaningful to most people, so I'll omit them.
[Note] According to the Church-Turing Conjecture, no formal language can= 
surpass the expressive power of a Turing machine. C can be considered 
a high-level language or "specification" of a Turing machine. Prop 1: Since a consecutive O(P) number of Ptime functions (or instructi= ons) can 
be combined into a single Ptime function, the above np algorithm is equivalent to the following np1 algorithm with a single for loop:
// begin_certificate is a Ptime function. 
// Extract the first Certificate element from problem statement q. If this<=
br />
// element does not exist, return the unique and virtual EndC element. 
// end_certificate is a Ptime function. 
// Extract the element EndC from problem statement q. 
Certificate end_certificate(Problem q);
// next_certificate is a Ptime function. 
// Extract the element after c from problem statement q. If this element<br=

// does not exist, return the EndC element. 
Certificate next_certificate(Problem q, Certificate c);
// v is a Ptime function. v(c)=3D=3Dtrue iff c is the element expected b=
y the 
// problem. 
bool v(Certificate c);
bool np1(Problem q) { 
Certificate c, begin, end; // Declare the verification data variable begin =3D begin_certificate(q); // begin is the first verification data 
// the end 
for(c=3Dbegin; c!=3Dend; 
c=3Dnext_certificate(q,c)) {// At most O(2^|q|) loops. next_certificate(c)<=
br />
// Ptime function for finding the next 
// verification data for c 
if(v(c)=3D=3Dtrue) return true; // v:C->{true,false} is a polynomial tim= e 
// verification function, 
} 
return false; 
}
Prop 2: =E2=84=95=E2=84=99 problems can always be split into two sub-pro= blems. 
Proof: The verification data set can be split into two and processed recursively as follows:
bool banp(Problem q) { 
if(certificate_size(q)<Thresh) { // Thresh is a small constant 
return solve_thresh_case(q); // Solve q in constant time 
} 
Problem q1,q2; 
split_certificate(q,q1,q2); // Divide the verification data set C in q 
// approximately abs(|q1|-|q2|<=3DO(1)) 
return banp(q1) || banp(q2); // Compute the sub-problems separately 
}
Prop 3: Any two =E2=84=95=E2=84=99 problems q1 and q2 can be combined in=
to another =E2=84=95=E2=84=99 problem q, 
which can be expressed as q=3Dq1=E2=8A=95 q2. The verification data set C a= nd 
verification function v for q are defined as follows:
C =3D C1||C2 // C1, C2 are the verification data sets for q1 and q2,<b=
r />
// respectively
bool v(x) { 
return v1(x) || v2(x); // v1, v2 are the verification functions for q1 
}
Prop 4: The banp(..) in Prop 2 above can add an object I (defined as a g= eneral 
form that stores information about how to accelerate the computation of a<b=
r />
problem to Ptime after completing the computation of a problem):
bool banp2(Problem q) { 
if(certificate_size(q)<Thresh) { 
return solve_thresh_case(q); 
} 
Problem q1,q2; 
split_certificate(q,q1,q2); 
Info I; // I stores information about accelerating the computation of the<b=
r />
// problem 
if(banp_i(q1,&I)=3D=3Dtrue) { // banp_i(q1,I) computes banp(q1) and 
// that can be derived from q1 into I. 
return true; 
} 
return solv_remain(q2,I); // Solve the remaining problem q2 given the 
// information in I. 
}
Prop 5: =E2=84=99=E2=89=A0=E2=84=95=E2=84=99 
Proof: From banp2, we can see that if the solution to a =E2=84=95=E2=84=99 = subproblem always 
provides I information that accelerates the computation of other subproblem= s 
,then due to the splitting and combining properties of the =E2=84=95=E2=84=
=99 problem, The I 
from a fixed-type problem of trivial problems is also valid for solve_remain(q2,I). In other words, I is effetively ineffective. Therefore,= 
no information I exists that can accelerate banp2 to Ptime.
For example, from q, we can construct q' of the same size and with a Pti= me 
algorithm. banp2(q=E2=8A=95 q') can always obtain I information at Ptime th=
at is not 
strongly correlated with q but can accelerate the computation of q by Ptime= . 
This is impossible.
The complexity of the banp (equivalent to np) algorithm is O(2^N). 
No algorithm exists that can accelerate the computation to Ptime, so =E2=84= =99=E2=89=A0=E2=84=95=E2=84=99.
<h2>+------------+ 
| References | 
+------------+ 
[1] THEORY OF COMPUTATION [Deric Wood] 
[2] ALGORITHMICS, Theory and Practice [Gilles Brassard, Paul Bratley] 
[3] AN INTRODUCTION TO FORMAL LANGUAGES AND AUTOMATA [Peter Linz] 
[4] <a href=3D"https://sourceforge.net/projects/cscall/files/MisFiles/Compu= tation-en.txt/download">https://sourceforge.net/projects/cscall/files/MisFi= les/Computation-en.txt/download</a> 
(Computing concepts and term definition)</h2>

--=-cVPsilWlsvBLtJlfaYOi--

--- Synchronet 3.21a-Linux NewsLink 1.2

Who's Online

System Info

P!=NP proof for review