Deutsch   English   Français   Italiano  
<82424399a48d4d3b203579b36a329a4e95ac834c.camel@gmail.com>

View for Bookmarking (what is this?)
Look up another Usenet article

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: Mon, 24 Feb 2025 07:14:42 +0800
Organization: A noiseless patient Spider
Lines: 111
Message-ID: <82424399a48d4d3b203579b36a329a4e95ac834c.camel@gmail.com>
References: <ce3f0c1fdbf0cc7212ca97edbd5f525c254a7c02.camel@gmail.com>
	 <vpfa11$2ti3o$1@paganini.bofh.team>
MIME-Version: 1.0
Content-Type: text/plain; charset="UTF-8"
Content-Transfer-Encoding: quoted-printable
Injection-Date: Mon, 24 Feb 2025 00:14:43 +0100 (CET)
Injection-Info: dont-email.me; posting-host="980b458187305953ab598c498197a9c5";
	logging-data="745035"; mail-complaints-to="abuse@eternal-september.org";	posting-account="U2FsdGVkX18hiU/0mytu5YxqqkS2RK8C"
User-Agent: Evolution 3.54.3 (3.54.3-1.fc41)
Cancel-Lock: sha1:Uk2A4wUdirbC1PS2a1+knIvnROc=
In-Reply-To: <vpfa11$2ti3o$1@paganini.bofh.team>
Bytes: 6600

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 modification fr=
om
> > 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 easier =
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 d=
oes 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 only r=
equire existence, not "given", and
> > =C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0 its false state has no time limit,=
 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. But t=
hese 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 Ptime a=
lgorithms 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 with =
the definition in the textbook, the
> > =C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0 conditions required by ANP are cle=
arer 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 elaborate =
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 regardless
> 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.

The purpose of this proof is to show that no polynomial algorithm exists th=
at
can solve NPC (real) problems. The goal is not the academic computation the=
ory.
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 level =
of
tape operations.

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 relative,
rarely an issue in discussion of C language).
Limitation is engineering things, but such limitation may actually be a goo=
d
thing. It links theory and reality. No matter how abstract the language/the=
ory
is, it eventually need to be materialized. An example about this is about
infinity, which is merely an infinite loop, others are all imagination.
https://sourceforge.net/projects/cscall/files/MisFiles/RealNumber2-en.txt/d=
ownload     =20
(Axiom0,1,2 seemingly were added in latter time, I don't like them now, the
purpose of that article was not making theory)