Path: ...!eternal-september.org!feeder3.eternal-september.org!news.eternal-september.org!eternal-september.org!.POSTED!not-for-mail
From: wij <wyniijj5@gmail.com>
Newsgroups: comp.lang.c
Subject: Re: A P!=NP proof for review.
Date: Tue, 25 Feb 2025 18:20:22 +0800
Organization: A noiseless patient Spider
Lines: 184
Message-ID: <55bd9a62e5a67aea90fc63a33b80a7293d403480.camel@gmail.com>
References: <ce3f0c1fdbf0cc7212ca97edbd5f525c254a7c02.camel@gmail.com>
	 <vpfa11$2ti3o$1@paganini.bofh.team>
	 <82424399a48d4d3b203579b36a329a4e95ac834c.camel@gmail.com>
	 <vpj4gi$3dkul$1@paganini.bofh.team>
MIME-Version: 1.0
Content-Type: text/plain; charset="UTF-8"
Content-Transfer-Encoding: quoted-printable
Injection-Date: Tue, 25 Feb 2025 11:20:24 +0100 (CET)
Injection-Info: dont-email.me; posting-host="056406fb70dd5451562b4f48fa52cf83";
	logging-data="1995007"; mail-complaints-to="abuse@eternal-september.org";	posting-account="U2FsdGVkX1+/lcRaTkhda3YWmiMFuuN3"
User-Agent: Evolution 3.54.3 (3.54.3-1.fc41)
Cancel-Lock: sha1:bNYMBAnaQeO63MKUS3RCyTpsrkM=
In-Reply-To: <vpj4gi$3dkul$1@paganini.bofh.team>
Bytes: 10485

On Tue, 2025-02-25 at 00:56 +0000, Waldek Hebisch wrote:
> wij <wyniijj5@gmail.com> wrote:
> > On Sun, 2025-02-23 at 14:06 +0000, Waldek Hebisch wrote:
> > > wij <wyniijj5@gmail.com> wrote:
> > > > This file is intended a proof that =E2=84=99=E2=89=A0=E2=84=95=E2=
=84=99. The contents may be updated anytime.
> > > > https://sourceforge.net/projects/cscall/files/MisFiles/PNP-proof-en=
..txt/download
> > > >=20
> > > > The text is converted by google translator with minimal modificatio=
n from
> > > > https://sourceforge.net/projects/cscall/files/MisFiles/PNP-proof-zh=
..txt/download
> > > >=20
> > > <snip>
> > > > =C2=A0 Note: Because there are many ways to define =E2=84=95=E2=84=
=99, the definition of ANP
> > > > =C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0 (Another NP) is to make it eas=
ier to deal with confusion. The general
> > > > =C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0 definition of =E2=84=95=E2=84=
=99 does not require O(2^N) loops and C sets. The
> > > > =C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0 verification function v may on=
ly require existence, not "given", and
> > > > =C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0 its false state has no time li=
mit, nor does it say that all elements of
> > > > =C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0 C must be tested one by one. B=
ut these are not important.
> > >=20
> > > Sorry, this is crucial element.
> > >=20
> > > > =C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0 What we care
> > > > =C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0 about is whether there are Pti=
me algorithms for various practical =E2=84=95=E2=84=99=E2=84=82
> > > > =C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0 problems. In fact, comparing w=
ith the definition in the textbook, the
> > > > =C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0 conditions required by ANP are=
 clearer and stricter, but the
> > > > =C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0 substantive meaning should be =
the same. This point has some subjective
> > > > =C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0 elements, so I will not elabor=
ate on it.
> > >=20
> > > The devil is in details.=C2=A0 It was observed (short after P versus =
NP
> > > problem was clearly formulated) that by generalizing problem and
> > > changing definitions one can make it go one way or the other.
> > > Precise formulation uses notion of computatiom with oracles: you
> > > are given an extra function F which solves some possibly hard problem=
,
> > > but you are "charged" only unit cost for using such a function.
> > > With one F we have P(F) =3D NP(F), with other F we (provably!) have
> > > P(F) !=3D NP(F).=C2=A0 Most methods of proving work the same regardle=
ss
> > > of F, so can not solve P versus NP.
> > >=20
> > > To illustrate some of troubles consider a silly C function below:
> > >=20
> > > bool right_guess(long i) {
> > > =C2=A0=C2=A0=C2=A0 return (i =3D=3D MAGIC_CONSTANT);
> > > }
> > >=20
> > > where MAGIC_CONSTANT is a fixed constant of type long.=C2=A0 Your
> > > task is to find i such that right_guess(i) returns true.=C2=A0 If
> > > you are allowed to look at MAGIC_CONSTANT, than the task is
> > > trivial, you just read the answer.=C2=A0 If you are only allowed to
> > > call right_guess, but are not allowed to look at MAGIC_CONSTANT,
> > > then problem is provably hard: you can not do better than looking
> > > at large fraction of possibilities.=C2=A0 P versus NP problem is
> > > analogous to "obfuscated C" problem: you are given source code
> > > of right_guess, but this source is written in obfuscated form,
> > > so that MAGIC_CONSTANT is not visible (actually, right_guess may
> > > be computing something quite different).=C2=A0 So in C terms, the
> > > P versus NP question is: can you de-obfuscate given function
> > > well enough to decide if it returns true for some value.
> > > Of course "can" means doing it in polynomial time and we
> > > assume that function can do its computation in polynomial
> > > time.
> > >=20
> > > Note: C is not good fit for theoretical problems because basic
> > > C type have fixed and rather small size.=C2=A0 For example current
> > > popular implementations have 32-bit int type.=C2=A0 Replacing
> > > long by int in right_guess we get problem which can be easily
> > > solved by brute force on normal PC.=C2=A0 Using implementation with
> > > 64-bit long we get problem which on current machines is
> > > realistically hard, but possibly solvable on bigger machines.
> > > Theoretical texts avoid such problems by using theoretical infinte
> > > machines (like Turing machine).=C2=A0 I hinted above at another
> > > possibility: with finite machines real question is we can
> > > find answer substantially faster than using brute force.
> > > But "substantially faster" would need more precise formulation
> > > and speed of real machines go beyond what C specifies.
> >=20
> > The purpose of this proof is to show that no polynomial algorithm exist=
s that
> > can solve NPC (real) problems.
>=20
> You did not prove anything non-obvious.=C2=A0 It is well-known that
> brute force search is exponential.=C2=A0 The real question is if
> there is a different faster method.=C2=A0 Have you ever looked at
> multiplication of large numbers?=C2=A0 Well-known method has
> quadratic complexity and lot of people assumend that it is
> is not possible to multiply faster.=C2=A0 But it is now known that
> one can do better and you find on the net mixed C/assembly
> code that multiplies large numbers "impossibly fast", that
> is in time much shorter than time needed to perform instructions
> in classical method.

Echo from the market place does not change anything. Refuting my proof P!=
=3DNP
is easy, showing ANP!=3DNP may be a good try: My 'NP' is defined on real pr=
oblems.=C2=A0
You may try to show some NP problem is not ANP, or ANP contains non-NP=C2=
=A0problem.

> Coming back to NP, standard problem is boolean satisfability.
> It is practial problem, for example its solutions are used
> to design digital chips.=C2=A0 Your "proof" essentially says that
> satifability problem with 200 variables, which amount to
> finding 200 bits will take of order of 2 to the power 200
> operation.=C2=A0 Easy estimations show that such complexity is
> out of reach on current computers (time would be bigger
> than age of our universe).=C2=A0 Now fetch from the net
> 'minisat' and try how much time it needs to solve problems
> with 200 variables.=C2=A0 I doubt that you will be able to
> create problem with 200 variables that is hard for 'minisat'.
> Actual practical experience is that 'minisat' (or similar
> but improved programs) typically can solve quite large
> satisfability problems, for example problems involving
> 1000000 variables.=C2=A0 But 'minisat' uses much smarter method
> than brute force and it takes advantage of specific
> problem formulation.=C2=A0 And sometimes 'minisat' fails to
> find soultion using available resources.=C2=A0 Both practical
> and theoretical problem is: can we improve 'minisat'
> so that it always works?=C2=A0 Proof of P !=3D NP would give
> stong indication that this is impossible.=C2=A0 Cryptographers
> have a different problem, they do _not_ want 'minisat'
> (or other methods) to be able to solve (break) their
> ciffers (AFAIK 'minisat' can not break real world
> ciffers, but to formulate problem in way acceptable
> to 'minisat' you probably need more than 200 variables).

I think you don't really understand what P and NP mean.

> > The goal is not the academic computation theory.
> > C/C++ programmer can immediately have idea what is going on there.
> > But I admit my proof is not good enough for request of detail to the le=
vel of
> > tape operations.
> >=20
> > C/C++ is no less appropriate (Knuth even uses assembly) for theory.
> > C has a strong tie with hardware, just like TM (in C, 'size' is relativ=
e,
> > rarely an issue in discussion of C language).
>=20
> C++ is fine if you want to demonstrate that problem has fast solution
> (which is main goal in Knuth books).=C2=A0 C++ is clumsy if you want to
> _prove_ that there are no fast solution.

If it refers to banp2(..). Then, why is it clumsy to prove in C++ (or C)
that "without additional information, banp in Ptime is impossible"?
Is there any more elegant way or language for this?

> > Limitation is engineering things, but such limitation may actually be a=
 good
> > thing. It links theory and reality. No matter how abstract the language=
/theory
> > is, it eventually need to be materialized. An example about this is abo=
ut
> > infinity, which is merely an infinite loop, others are all imagination.
>=20
> You have strange thoughts about infinity.=C2=A0 Theoreticians use infinit=
y
> because it is easier and gives valuable insight into finite things.
> Real world is messy and contains a lot of details which should be
> irrelevant for problem that we want to solve.=C2=A0 Using infinity allows
> simpler formulation which omits most of details, leaving only
> what metters.=C2=A0 Tu put it differently, infinity is a fiction, but
========== REMAINDER OF ARTICLE TRUNCATED ==========