info
Google Groups no longer supports new Usenet posts or subscriptions. Historical content remains viewable.
Dismiss
Easy version of P!=NP proof
18 views
Skip to first unread message
wij
Jan 31, 2024, 9:51:04 AMJan 31
to
ANPC::= (Another NPC) Set of decision problems that additional
information c must be provided to compute the problem
in P-time (including processing the information c).
Since the information c can be generated in O(2^N) time, the
upper bound of ANPC is O(2^N) (checking c is in P-time).
If we try to prove or show ANPC==P, then we would also have
proved/shown that the request of the additional information c is
not necessary. But, since the request is necessary by the definition
of ANPC, such proofs will never be valid.
Conclusion: ANPC is not P-time solvable.
Corollary: If TSP/3SAT/... are ANPC problems, then, NP!=P.
-------
PS. I should have posted a similar version of such proof 6-month
ago, olcott's new idea "invalid question" reminded me of
this problem, because P-NP problem has some kind of similarity.
information c must be provided to compute the problem
in P-time (including processing the information c).
Since the information c can be generated in O(2^N) time, the
upper bound of ANPC is O(2^N) (checking c is in P-time).
If we try to prove or show ANPC==P, then we would also have
proved/shown that the request of the additional information c is
not necessary. But, since the request is necessary by the definition
of ANPC, such proofs will never be valid.
Conclusion: ANPC is not P-time solvable.
Corollary: If TSP/3SAT/... are ANPC problems, then, NP!=P.
-------
PS. I should have posted a similar version of such proof 6-month
ago, olcott's new idea "invalid question" reminded me of
this problem, because P-NP problem has some kind of similarity.
0 new messages