Rocksolid Light

Welcome to Rocksolid Light

mail  files  register  newsreader  groups  login

Message-ID:  

If Machiavelli were a hacker, he'd have worked for the CSSG. -- Phil Lapsley


devel / comp.theory / Easy version of P!=NP proof

SubjectAuthor
o Easy version of P!=NP proofwij

1
Easy version of P!=NP proof

<4dc1f5fe24724be0543663e34f66157fd65434f9.camel@gmail.com>

  copy mid

https://news.novabbs.org/devel/article-flat.php?id=53046&group=comp.theory#53046

  copy link   Newsgroups: comp.theory
Path: i2pn2.org!i2pn.org!news.hispagatos.org!eternal-september.org!feeder3.eternal-september.org!news.eternal-september.org!.POSTED!not-for-mail
From: wyniijj5@gmail.com (wij)
Newsgroups: comp.theory
Subject: Easy version of P!=NP proof
Date: Wed, 31 Jan 2024 22:50:58 +0800
Organization: A noiseless patient Spider
Lines: 22
Message-ID: <4dc1f5fe24724be0543663e34f66157fd65434f9.camel@gmail.com>
MIME-Version: 1.0
Content-Type: text/plain; charset="UTF-8"
Content-Transfer-Encoding: quoted-printable
Injection-Info: dont-email.me; posting-host="92fa55fd98e20191267da13195eabd08";
logging-data="1654972"; mail-complaints-to="abuse@eternal-september.org"; posting-account="U2FsdGVkX19mlUX4SPLhZTsRKBgJ7+5E"
User-Agent: Evolution 3.50.2 (3.50.2-1.fc39)
Cancel-Lock: sha1:Xc+qVknJkcNJiN0z7WJ/DdDW1/E=
 by: wij - Wed, 31 Jan 2024 14:50 UTC

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.

1
server_pubkey.txt

rocksolid light 0.9.81
clearnet tor