ANP= {q| q is an algorithmic decision problem. If information c (O(|c|)=O(|q|))
is given, q can be computed in P-time} // ANP=NP?
P= {q| q is an algorithmic decision problem. q can be computed in P-time}

Proof ANP!=P: From ANP definition, if c, equivalent to unknown information, is
absent, for ANP to equal to P, the algorithm can only resume this deficiency
by one-by-one-generate-and-test method to find the information c. Since there
are O(2^N) possibilities, ANP has to be computed in O(2^N) steps. Otherwise,
the unknown information c being able to be computed in P-time will lead to a
condition that such an unknown information c is not required, then the
definition that c must be provided to enable P-time computation is violated.

QED.

Therefore, I think P!=NP may be proved. Any 'hole' of the idea?
Note that this proof stresses on that the set ANP is *defined* to be solved in
O(2^N) steps. I don't have any direct proof why any of the more concrete NPC
problems like SAT,TSP,... cannot be solved in P-time, which is provided in text
book theory.

wij <wyniijj5@gmail.com> writes:

> ANP= {q| q is an algorithmic decision problem. If information c (O(|c|)=O(|q|))
> is given, q can be computed in P-time} // ANP=NP?
> P= {q| q is an algorithmic decision problem. q can be computed in P-time}
>
> Proof ANP!=P: From ANP definition, if c, equivalent to unknown information, is
> absent, for ANP to equal to P, the algorithm can only resume this deficiency
> by one-by-one-generate-and-test method to find the information c. Since there
> are O(2^N) possibilities, ANP has to be computed in O(2^N) steps. Otherwise,
> the unknown information c being able to be computed in P-time will lead to a
> condition that such an unknown information c is not required, then the
> definition that c must be provided to enable P-time computation is violated.
>
> QED.
>
> Therefore, I think P!=NP may be proved. Any 'hole' of the idea?

Yes, you assume that P != NP in the proof. You need to prove, rather
than state that determination of c (the "hint" that allows q to be
decided in polynomial time) takes O(2^|c|) time. Finding /any/ problem
that, provably, can not be in P is what's needed so you can't just state
that this is true of determining c (given q).

--
Ben.

On Sunday, June 18, 2023 at 7:27:32 PM UTC+8, Ben Bacarisse wrote:
> wij <wyni...@gmail.com> writes:
>
> > ANP= {q| q is an algorithmic decision problem. If information c (O(|c|)=O(|q|))
> > is given, q can be computed in P-time} // ANP=NP?
> > P= {q| q is an algorithmic decision problem. q can be computed in P-time}
> >
> > Proof ANP!=P: From ANP definition, if c, equivalent to unknown information, is
> > absent, for ANP to equal to P, the algorithm can only resume this deficiency
> > by one-by-one-generate-and-test method to find the information c. Since there
> > are O(2^N) possibilities, ANP has to be computed in O(2^N) steps. Otherwise,
> > the unknown information c being able to be computed in P-time will lead to a
> > condition that such an unknown information c is not required, then the
> > definition that c must be provided to enable P-time computation is violated.
> >
> > QED.
> >
> > Therefore, I think P!=NP may be proved. Any 'hole' of the idea?
> Yes, you assume that P != NP in the proof. You need to prove, rather
> than state that determination of c (the "hint" that allows q to be
> decided in polynomial time) takes O(2^|c|) time. Finding /any/ problem
> that, provably, can not be in P is what's needed so you can't just state
> that this is true of determining c (given q).
>
> --
> Ben.

Refine ANP:
ANP={q| q is an algorithmic decision problem. If given additional information c
(including not given), q can be computed in P-time.
Specifically, q(n)=1 iff exists c such that a P-time decision function
v(n,c)=1, where v is a given function and:
v(n,c): S×S' ->{0,1}, where S={0,1}^N, S'=S∪{_}. n= problem argument,
c= the given info. (certificate), '_' means empty.
}

If the information c could be generated in P-time, then this P-time generating
function and the function of v can be merged to form a new verification function
v', so that v'(n,_) is equivalent to v(n,c). Thus, a q equivalent problem q'
using v' exists, q' does not need the c information to be in P-time.

Therefore, IF c IS REQUIRED, c must be computed in O(2^N) steps, because the
other cases are equivalent to the cases that c can be absent (I assumed that no
asymptotic class exists between P and O(2^N) and ANP=NP).

Since the worst case of q in ANP has to generate O(2^N) 'guesses' for c, ANP is
bounded by O(2^N) is concluded.

This proof just shows ANP problem solving is bounded by O(2^N). This ANP!=P
proof is quite indirect in that it does not explicitly show how NPC problems
have to be solved in O(2^N) makes me nervous. But the logic (though not well
formalized) looks to me OK. Any logic flaws?

wij <wyniijj5@gmail.com> writes:

> Refine ANP:
> ANP={q| q is an algorithmic decision problem. If given additional information c
> (including not given), q can be computed in P-time.
> Specifically, q(n)=1 iff exists c such that a P-time decision function
> v(n,c)=1, where v is a given function and:
> v(n,c): S×S' ->{0,1}, where S={0,1}^N, S'=S∪{_}. n= problem argument,
> c= the given info. (certificate), '_' means empty.
> }

This is now very close to the definition of NP, but that's not really
important.

> If the information c could be generated in P-time, then this P-time
> generating function and the function of v can be merged to form a new
> verification function v', so that v'(n,_) is equivalent to
> v(n,c). Thus, a q equivalent problem q' using v' exists, q' does not
> need the c information to be in P-time.

I don't like how you put it, but yes.

> Therefore, IF c IS REQUIRED, c must be computed in O(2^N) steps,
> because the other cases are equivalent to the cases that c can be
> absent (I assumed that no asymptotic class exists between P and O(2^N)
> and ANP=NP).
>
> Since the worst case of q in ANP has to generate O(2^N) 'guesses' for
> c, ANP is bounded by O(2^N) is concluded.
>
> This proof just shows ANP problem solving is bounded by O(2^N).

We know this anyway from the definition of NP.

> This ANP!=P
> proof is quite indirect in that it does not explicitly show how NPC problems
> have to be solved in O(2^N) makes me nervous. But the logic (though not well
> formalized) looks to me OK. Any logic flaws?

I can't see any way in which this is a proof that ANP != P. We already
know the upper bound for the complexity of problems in NP (and in ANP)
but nothing here gives a lower bound.

--
Ben.