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)