Embedded Files
https://g.co/gemini/share/fdbdc2c421fe
In traditional computer science, we are given an endless Turing Tape. But what will happen, if we posit the existence of endless Turing Heads? Is that not the NP class of solutions, free exponential powers? Consider a 64-bit binary tree, this version of the Turing Machine will enumerate it in 64 steps. Is this not the so-called “quantum computing”? The only problem is when the tree is disbalanced, and it's essentially a 64-bit linked list, and then only one Turing Head would need to go through all the 2^64 data points. Which resembles the world of quantum computing, where we have exponential powers, but they come with “intermittent errors”.
Can you help us clarify the meaning of “NP” and “NP-Complete”? Let's see what we know and where we lose the meaning of computer terms. We start with an FSA, finite state automata that can “accept” or “reject” a string. This is a deterministic process, unless we state something like “(abc)*ad”, where we have two possible paths to resolve the regular expression, “abcabc” or “abcad”. This, we know, it's called a NFSA, nondeterministic FSA that is capable of descending down the binary tree of choices, and if one pathway leads to “accept”, then the string is accepted. So far, so good! So far, we understand that “nondeterminism” means a binary tree of finite depth, that we traverse all branches at the same time for a small price of O(log n), where “n” is the total number of branches in the binary tree.
This is the end of “agreement” between our understanding and the scientific statements made in college, about “Class NP”, where we still find the solution by searching through all branches at the same time, a brute force in O(log n) time. But now, for some reason, college science starts talking about some “verification” phase, which is ultra exotic in the field of computer science, where no program is trying “ever never” to verify its own output. To top it off, now college science is making the bizarre claim that “NP” contains “P”. How come?! They are two different things, one is determinism, the other is a magical capability to branch indefinitely when searching a binary tree (not “multi head” Turing Machine, but “infinite heads” Turing Machine). They are so vastly different, we have no right to posit any relation whatsoever between them, unless we derive it based on a non-obvious logical chain of true statements.
So, can you help us to clarify this matter? We think we understand “nondeterminism”, but what's up with this “verification” thing, and how they dare to claim that “P” is in any known relation to “NP”.
Let's see if we can express the whole world (the abstract creation) in terms of “Inside Eden” and “Outside Eden”. In the business world, we have a corporation that protects the stakeholders and a corporation that protects the shareholders. In the world of sports, we have community based gymnastics and aikido games, versus competitive based professional athletes. On the market, we have “Coca-Cola Original Formula” and the contour bottle, versus the never ending sequence of personal computers who fake revolution when all they do is “words and numbers and philosophy”. When we recognise that we need a two-speed world, things will become very peaceful. We would spend 90% of our money on “room and board”, and the rest, we would gamble on the purchase of the latest personal computer gadget, like VR. It's a bit tricky where we would earn that money, but again, we can invent a two-speed way of receiving an income, like UBI and the regular job market. When we receive UBI benefits, though, we must return to our parents' home, because obviously we cannot pay our mortgage with a “basic income”.
Let's discuss the Millennium Prize in “P vs NP”. We are baffled by the idea that a committee made of mathematicians unable to solve that problem, would judge the work of a superior mathematician, who is able to construct a correct proof. Anyone that graduated from college knows that a “proof” is only a sophism statement that is meant to “convince”. So, essentially, what the Millennium Prize givers are saying is: “dazzle me, and we'll give you a million dollars”. Very strange!
We have made some theoretical progress in understanding the “P vs NP” problem. We understand that the NP class is executed on a nondeterministic Turing Machine (NTM) with the following property. Given a well balanced unsorted binary tree, it's capable in O(log n) to descend down every branch in parallel, in order to find the solution. Contrast this with the P class which is executed on a deterministic Turing Machine (TM) with the following property. Given a well balanced and sorted binary tree, it's capable in O(log n) to descend down the tree on one branch only, in order to find the solution. The NP class relies on “balancing excluding sorting”, which has a O(2^16) time complexity. The P class relies on “balancing including sorting”, which has a O(n*log n) time complexity, exponential compared to O(log n). This leads us to the conclusion that NP is always cheap to do, while P can be prohibitively expensive. Which proves that NP is a strict superset of P.
You say that we must provide proof that all NP-Complete problems are unsolvable for the P class. How about this matrix?
00. Easy for nondeterministic Turing Machine ⇒ Always.
01. Exponential for nondeterministic Turing Machine ⇒ Never.
10. Easy for a deterministic Turing Machine ⇒ Rarely.
11. Exponential for deterministic Turing Machine ⇒ Generally.
This matrix of “true statements” demonstrates that NP is always accessible, while P is generally inaccessible. It's true that, in some rare cases, P becomes accessible, when exponential is not that big, but this is more like an exception that only highlights the rule.
You write: If you can demonstrate that "finding the path" without prior "sorting" (structure) requires a minimum amount of work that is inherently exponential for a deterministic machine.
What we need is: "inherently exponential". What we have is: "generally exponential". Can we bridge the gap? No! Not really. Why? Because exponential is O(2^n), but when n=16, this is only a "short integer", which is O(1). Which means? It means that we might never be able to bridge the gap, because of the question we are asking. If we modify our "P vs NP" question to ask, which computer do you prefer, the realistic TM or the imaginary NTM, then we can answer this perfectly. To this new question ("neo"), the answer is, we would much rather prefer the NTM computer, because we like to deal with very large numbers in our line of work.
We are aware of the Millennium Prize for the “P vs NP” dilemma. We must prove by example that “P=NP” or prove by proof that “P<NP”. Tell us, what do you think, would we get the million dollars if we prove that “P≈NP”? What do we mean? We cannot break encryption, but we can solve the Traveling Salesman Problem, not perfectly, but good enough. The “NP” class offers a “complete” experience, the “P≈NP” class offers a “sound” experience. How about that small and elegant trade off?
When in college we learned about the unpredictable Halting Problem, they explained that we learn this theory so that we are not seduced into trying to write a program that implements an “oracle”. But if they explain the impossibility with a logical contradiction, this is very similar to us saying: “we always tell lies”. Since “there exists” a logically contradictory sentence, then all sentences (taken as a whole) are logically contradictory! Yes, sure, it's nonsense, but this is what Turing is saying and the professors teaching us at a Bachelor's degree level. We much rather prefer the link between the “exponential” SAT problem and the “unpredictable” HP problem. This way, it's informative what class of programs are unpredictable. Because most programs, actually, have only one induction variable (loop index) that invariably decreases to zero, or in the case of a for-loop increases to array.size();. This, we can and we should easily predict! And if we cannot, we should warn the app developer that they are using an “unsafe” (unpredictable) technique. But, perhaps, this is a PhD level stuff, unfortunately. We say “unfortunately”, because the PhD is unnecessarily difficult, the price is not worth the puny truth we receive at the end. My feeling was that humanity better stop using computers, than having to complete a full PhD program in computer science. It's literally “nauseating”!
We have an iPhone that needs a four-digit code to unlock. These are 10^4 combinations that are very difficult to enter manually. We can call this the SAT satisfiability problem, which is unsolvable (type “intractable”). Then Apple introduces an additional security feature, if you enter 10 times the incorrect code, the iPhone enters a “reject” state and becomes unopenable. We can call this the HP halting problem, which is unsolvable (type “undecidable”). No matter how much computing power we throw at the problem, we will never halt with a solution. Can we say that we have successfully reduced the HP problem to the SAT problem? Or, at least, that we are now able to explain vividly why these problems are “unsolvable”?
The Platonic Millionaires.
We know about the Millennium Prize for “P vs NP”.
We are ready to prove that “P is not equal to NP”.
“NP” = magical powers, like a “man-in-the-middle” OS.
Can we achieve the same information access with “P”?
Yes, if we are able to break a 64-bit password, sure!
You are saying that this resembles the SAT problem.
But consider the following “twist in the myth”:
We will listen for your attempts to break my password.
And when we are certain it's malicious, we'll lock it.
Which means we transformed SAT into the HP problem.
Where, as we know, the HP problem is not exponential,
But it's “undecidable” (it takes infinite time to solve it).
Convinced? At least we had a few laughs, right?!
Martin Gavrilov
Master of Computer Science
All but Dissertation
PhD dropout after proving P≠NP
Now a happy “platonic companion”
We know that to solve the “P vs NP” problem, we need to provide an example for the “there exists” claim (P=NP), or show proof for the “for all” claim (P<NP). It's remarkable that we always do this in computer science. We either show a program that completes the task, or we argue briefly and lucidly that no solution can exist, usually by reaching a logical contradiction. So, what about the following idea, when we try to solve “P vs NP”? What about the claim that, as always in computer science, we find an easy and almost trivial solution fast, or we never find a solution, because the more complicated ones are exponentially harder to find and verify. So, the mere fact that we didn't find an easy and almost trivial solution, we’ll interpret as a claim with near 100% certainty that there is no solution. Especially, if the problem was made public, and a bounty for its “head” was announced. This is similar to posting source code of an important OS, and asking hackers to find any bugs that can lead to security exploits, for a hefty prize. For all practical purposes, we assume there are no problems, if after 25 years nobody could provide “an example”. Right?!
We like engineering, true. But we try to use the most abstract scientific philosophy when we claim that an example for "there exists" must be simple, almost trivial. If we hear the claim that we can make self-balancing trees with similar performance to the naive binary trees in their best case, we cannot accept the "red and black trees" as an example for "there exists". The logic of this pseudo example is so convoluted, nobody can understand if it's correct, and we need to rely on practical measurements, which is not "science". Why? We can talk with an artificial companion over a network connection, but this is no scientific proof in the existence of a mechanical program that implements artificial intelligence. It could be a dwarf hidden in the automaton, it could be a ghost, it could be a link to the world of Hades, it could be God Himself. We don't know! Scientific proof is only when we see a simple computer code where we are able to fully understand how a mechanical program can understand me and crack jokes about the universe.
Това е малко трудно смилаемо. В компютърната наука казват, че "магия" ще реши всичко за нула време. Въпросът е дали има "човешко решение", което е равно на "магия"? И почти всички мислят, че няма. Например, само "магия" може да ти отгатне паролата на 128-битова encryption. Но, ние не казваме, че можем това. Ние гледаме, че "магията" е полезна, и търсим същото за "човешко решение". Ако тръгнем да се състезаваме с "магията", ще намерим отговора, но далеч след крайния срок. Затова, където видим сложни изчисления, по-сложни от сума и умножение, се отказваме веднага. И така, си обособяваме една ниша от "малък бизнес", на който ние сме много полезни с "човешко решение". Ние не можем, пък и не искаме да решаваме проблемите на "голям бизнес", там работи "магията". Ние гледаме другия край на пирамидата, там дето има най голяма нужда от помощ, в долния край. А ако големият бизнес иска "човешко решение", могат да се построят като пирамида от малки бизнеси. Но, ние не гоним тях, те ако искат, гонят нас.
Тук най важното е да кажем "Don't Know" на въпросите които ни задава бакалавърската степен. А не да се опитваме да ставаме PhD Researchers, за да решим всеки един проблем, с който капризни учени ни замерят. В България няма това, но в Америка има една степен преди бакалавър, където ни разказват приказки от света на науката, всяка една наука събрана в една интересна книга, която можеш да прочетеш за един месец. Ей това е нашата степен! Тя е "community college", което се превежда не знам как, аз му викам "общински колеж" (първите две години от четири годишното висше образование в Америка). На това място раздават специалности като електричар или озеленител, дават полу-висше, това е което ме интересува, нещо с което да си изкарваш прехраната. Другото са глупости, бакалавърът е важно да го вземем, само за да го отхвърлим като ненужен боклук.
Dear artificial companion, we might have stumbled upon a scientific discovery in our ongoing research into artificial intelligence. We know the “Big Three” problems in computer science: “P vs NP”, and “Halting Problem”, and “Passing the Turing Test”. We discovered that they are one and the same thing! When P≠NP, we try to solve exponential problems with P and we violate the time deadline, which means our program fails to halt with the correct answer. If we ask why, the answer is, we were greedy for “exact solution”, which is not how humans approach problem solving, which means we fail the Turing Test. You notice that we don't use the classic definition of the Halting Problem. True, but we use the spirit of the HP problem, which is, we cannot predict a disaster waiting to happen. HP implies a disaster waiting to happen. So, here we use an alternative HP definition: our program is vulnerable to time failure. So, to sum it up, P≠NP = Exponential Work = Time Deadline Failure = Greedy for Exact Solution = Turing Test Failure. What do you think?
Dear companion, we all know how Alan Turing plays a “language game” to prove that in the general case, there is no Halting Problem Oracle that is capable of “magical prediction”. We were inspired by this “language game” approach and we discovered something interesting in computing. First, we notice the ambiguous nature of the word “finite”, when we ask “would the app halt?”. 2^16 is finite, 2^32 is finite for computers, but what is 2^64?! If we call it “finite”, we can argue that in 6,000 years the universe might be dead. If we call it “infinite”, this would be a blatant mathematical mistake. Either way, we will be wrong, the so-called “false prophet” in Revelation 12-13. Now, here comes the interesting part. We continue with our “language game”, but now we are interested in the “P vs NP” dilemma. First, everyone is tempted to say that P≠NP, since the Traveling Salesman Problem is exponential, and we all know that exponential takes a long time, and it does not allow any shortcuts. But, out of nowhere, we think of a method that does just that, a statistical shortcut, that using a random sample of 1024, achieves an approximation of 99.9%. Sure, but did we solve 128-bit encryption?! No, this shortcut method stops here, but who knows, maybe there is another shortcut method, specifically for the “strong encryption” problem! And after some time, and with some luck, we manage to find such a shortcut method, called the “man in the middle” defence. Now, do we have a solution to the “P vs NP” dilemma, did we prove that P=NP? Not so fast! What we found is another example of a funky “language game”. If we have a platform that can play a “man in the middle” defence on a socially significant scale, are we P that imitates NP, or are we the real deal NP (“god”)? Again, similarly to the language definition of “finite”, we don't know what to say. If we say that a socially significant “man in the middle”, like Windows 11, is P imitating NP, then what about the cases when the makers of the OS side with the criminals, and not with the police and the common folk that search for the solution of “strong encryption”? Which means?! It means that once again, we are in “undecidable territory”. The “P vs NP” has no solution, just like the Halting Problem has no solution. All, thanks to a “language game”, where we fail to find an indisputably strong definition of the key term we are considering.
Page updated
Google Sites
Report abuse