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 ℙ≠ℕℙ. The contents may be updated anytime.
https://sourceforge.net/projects/cscall/files/MisFiles/PNP-proof-en.txt/download
The text is converted by google translator with minimal modification from >> > https://sourceforge.net/projects/cscall/files/MisFiles/PNP-proof-zh.txt/download
<snip>
Note: Because there are many ways to define ℕℙ, the definition of ANP
(Another NP) is to make it easier to deal with confusion. The general
definition of ℕℙ does not require O(2^N) loops and C sets. The
verification function v may only require existence, not "given", and
its false state has no time limit, nor does it say that all elements of
C must be tested one by one. But these are not important.
Sorry, this is crucial element.
What we care
about is whether there are Ptime algorithms for various practical ℕℙℂ
problems. In fact, comparing with the definition in the textbook, the
conditions required by ANP are clearer and stricter, but the >> > substantive meaning should be the same. This point has some subjective
elements, so I will not elaborate on it.
The devil is in details. 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) = NP(F), with other F we (provably!) have
P(F) != NP(F). Most methods of proving work the same regardless
of F, so can not solve P versus NP.
To illustrate some of troubles consider a silly C function below:
bool right_guess(long i) {
return (i == MAGIC_CONSTANT);
}
where MAGIC_CONSTANT is a fixed constant of type long. Your
task is to find i such that right_guess(i) returns true. If
you are allowed to look at MAGIC_CONSTANT, than the task is
trivial, you just read the answer. 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. 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). 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.
Note: C is not good fit for theoretical problems because basic
C type have fixed and rather small size. For example current
popular implementations have 32-bit int type. Replacing
long by int in right_guess we get problem which can be easily
solved by brute force on normal PC. 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). 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 that can solve NPC (real) problems.
You did not prove anything non-obvious. It is well-known that
brute force search is exponential. The real question is if
there is a different faster method. Have you ever looked at
multiplication of large numbers? Well-known method has
quadratic complexity and lot of people assumend that it is
is not possible to multiply faster. 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.
Coming back to NP, standard problem is boolean satisfability.
It is practial problem, for example its solutions are used
to design digital chips. 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. Easy estimations show that such complexity is
out of reach on current computers (time would be bigger
than age of our universe). Now fetch from the net
'minisat' and try how much time it needs to solve problems
with 200 variables. 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. But 'minisat' uses much smarter method
than brute force and it takes advantage of specific
problem formulation. And sometimes 'minisat' fails to
find soultion using available resources. Both practical
and theoretical problem is: can we improve 'minisat'
so that it always works? Proof of P != NP would give
stong indication that this is impossible. 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).
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 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).
C++ is fine if you want to demonstrate that problem has fast solution
(which is main goal in Knuth books). C++ is clumsy if you want to
_prove_ that there are no fast solution.
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 about infinity, which is merely an infinite loop, others are all imagination.
You have strange thoughts about infinity. Theoreticians use infinity
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. Using infinity allows
simpler formulation which omits most of details, leaving only
what metters. Tu put it differently, infinity is a fiction, but
a very useful one.
--
Waldek Hebisch
--- SoupGate-Win32 v1.05
* Origin: fsxNet Usenet Gateway (21:1/5)