I have made several tries of the P-NP proof, this is the 'official'
version I
think tough enough to withstand tests. But, of course, just an one-
sided view,
deficiency should exist.
The main idea behind the proof should be clear, easy to understand and
to use,
e.g. The theorem may be used to identify NPC problems 'intuitively'.
------------------- ℙ≠ℕℙ proof ('official')
This file is intended a proof that ℙ≠ℕℙ. The contents may be updated
anytime.
https://sourceforge.net/projects/cscall/files/MisFiles/PNP-proof.txt/download
Algorithmic problem::= The kind of problem that the size (length) of
the
argument of the problem is variable, so that the steps of
computation can
be expressed in asymptotic approximation.
ANP::= Set of decision (algorithmic) problem that the 'yes' answer can
be
verified in P-time from O(2^N) possible candidates of certificates,
where N
is the length of the problem's argument.
Precisely, ANP is a set of 3-tupple <ProblemArgs, Certificate,
Verify> that
can be computed by a pseudo-C program template npf(n):
ProblemArgs::= Problem arguments
Certificate::= Set of certificate. #Certificate= O(2^#ProblemArgs).
(three access methods for iterating elements of
Certificate
are required, see npf(n))
Verify::= A P-time decision function v:ProblemArgs×Certificate ->
{0,1}
bool npf(ProblemArgs n) {
Certificate c,begin,end;
begin= get_begin_certificate(n);
end = get_end_certificate(n);
for(c=begin; c!=end; c=next(c)) { // O(2^|n|) loop
if(v(n,c)) return true; // v(n,c), the verification is in P-
time
}
return false;
}
Note: If the C-code is not too fancy and close to Assembly, C-code
can
denote the same thing as TM. Another reason using C-code: The
'false'
answer of NDTM is visible in procedure npf(n).
Note: The for loop in npf(n) may include nested loops for sets like
S=S1xS2xS3x... as implied in NDTM model.
Property-independent::= Let x∈S, if ∀y∈S, y≠x, the evaluation result of
P(y) is
irrelavent to that of P(x), then, the property P of x is
property(P)-
independent. E.g. in the above case of npf(n), there may be cases
that the
result of v(n,x) is independent of the result of v(n,y), where, x≠y.
If the
number of such property(v)-independent elements are statistically
significant, such a set may be referred to as property(v)-
independent set.
Take 3SAT for another instance, the evaluation (property) of
different set of
boolean variable assignments are independent of each other.
Theorem: Finding an element x that P(x)==true in a property(P)-
independent set
S needs #S steps in the worst case.
Proof: Because property P is independent, computation steps
involving
testing the property P of/for each element of S is inevitable.
Therefore, #S
steps are necessary to get all the property P information of S.
Conclusion: Set Certificate is property(v)-independent, finding element
that
v(n,c)==true needs O(2^N) steps (worst case), therefore ANP ⊈ ℙ.
Since ANP==ℕℙ, therefore, ℕℙ≠ℙ.
QED. ----------------------------------------------------------------