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. ----------------------------------------------------------------

On 21/02/24 14:11, wij wrote:
>
> 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.
> to check each possible way to shuffle the list,
> 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. ----------------------------------------------------------------
>
>

I think polynomial-size certificates are also allowed in NP.

You can't prove that finding an element by checking one-by-one is the
fastest way to solve a problem. For example, to sort a list, one way is
to try shuffling the list every possible way, and then check if it's
sorted each time. Eventually you will shuffle the list in the right way
to sort it. This takes non-polynomial time. However, there are other
ways to sort lists in polynomial time.

wij <wyniijj5@gmail.com> writes:

Your argument is just the usual "I can't think how it could /not/
involve looking at at all the possible answers" argument. This is not
how a proof works. I'll point out the step where you just assume that
it mist be so:

> 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.

Here. This is just an assertion.

> 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. ----------------------------------------------------------------

--
Ben.