P=NP and Bitcoin
The present value of working on conjectures…
Anil Nerode of Cornell University has served over sixty years—he’s believed to be the longest such faculty member in university history. He helped found Cornell’s computer science department, advised more than 55 doctoral students—a Department of Mathematics record—and made important contributions to logic, mathematics, computer science, and more. He and Juris Hartmanis jointly oversaw Ken’s Mathematical Sciences Institute postdoc at Cornell in 1986–89.
I found it interesting that Anil has worked on teaching methods:
“I was educated at Chicago under the business of doing the cleanest, shortest expositions of absolutely everything,”
He has developed his own method: He now teaches in historical order. Translating ancient theories into modern notation allows him to show his students the origins of mathematics. This is a cool method.
|
| Cornell Chronicle source—our felicitations |
Anil has done extensive work in complex control systems, which is certainly a challenging area for an approach based on clarity and simplicity. He is often credited for co-creating, together with Wolf Kohn, an approach called hybrid systems theory. His partnership with Kohn has even extended to integrating quantum and macroscopic control mechanisms for magnetic batteries on many scales.
Conjectures Which Way?
Anil once said:
Being attached to a speculation is not a good guide to research planning. One should always try both directions of every problem. Prejudice has caused famous mathematicians to fail to solve famous problems whose solution was opposite to their expectations, even though they had developed all the methods required.
I blogged about this point in posts titled “We All Guessed Wrong” and “Even Great Mathematicians Guess Wrong”—and about other cases of surprises and about guessing the right side of conjectures.
But events this week have put a transverse thought into my head. The two sides of a conjecture may not be equal in their ramifications. This leads to a further weird thought:
Maybe the greatest overall value is in working hard on the side that you don’t want to be true—and hoping not to solve it.
The fact of Bitcoin hitting a new all-time high this week leads me to muse further about this.
Trillions
If you think you have a proof that P=NP then it is worth a lot of money. Well for sure, at least, you will get a prize like the Turing Award. But because it would break bitcoin and other digital monies you would possibly get into the thicket of billions of dollars. Maybe more like trillions.
|
| source |
Exactly what it would be worth to you, I don’t know. That’s a hypothetical. But there is a non-hypothetical that, from the understanding Ken and I have of how hedge transactions are valued, implies that one side of “P=NP” has clear and present monetary value:
What is the present value of not knowing that P=NP, and of exerting work that furthers the general sureness of this status?
A 2022 article titled “P = NP: The Dangling Blackhole Under Crypto” puts the stakes in stark terms:
P=NP is [about] whether a problem (in the case of Cryptocurrencies, a transaction) can be solved procedurally and systemically just as quickly as it can be verified with a hash. The security of the blockchain, such as [for] Bitcoin, is wholly dependent on the assumption that P does not equal NP. However, if P = NP is proven, the Bitcoin can be breached just as quickly as it can be authenticated.
A breach would have the kind of concrete effect we have in mind when we say, “from dollars to donuts…“—although the donuts involved could technically come from work like this:
|
| source |
Open Problems
Is it sensible to assign a present value to work on one side of the P=NP question? More than work that tries to establish the other side?
This is a well-known NP-complete problem:
We reduce this problem to MWX2SAT in polynomial time and so, MWX2SAT is in NP-complete as well. This is the definition:
INSTANCE: An
-variable 
formula with monotone clauses (meaning the variables are never negated) using logic operators 
(instead of using the operator 
) and a positive integer 
.
QUESTION: Is there exists a satisfying truth assignment in which at most
of the variables are true?
We prove this problem can be solved in polynomial time. See the proof here:
https://hal.science/hal-04420462
Moreover, we create our software programming implementation in Python:
https://github.com/frankvegadelgado/alma
Quote by Saint Augustine: The truth is like a lion. You don’t have to defend it. Let it loose. It will defend itself.
And how does it relate to cryptography?
Trying to convince the Google AI (Gemini) that P = NP
This is really hard to do 🙂
https://g.co/gemini/share/3a0f2d7cb012
My Question:
Does the phrase “either
or 
” actually means (
or 
) or (
or 
)?
Google AI (Gemini) Answer:
Yes, the phrase “either u ∈ V’ or v ∉ V'” does mean the same as:
(u ∈ V’ or v ∈ V’) or (u ∉ V’ or v ∉ V’)
Here’s the breakdown:
The original statement offers two possibilities:
However, the intent is to convey that only one of these conditions needs to be true, not both.
Therefore, rewriting it as two separate “or” statements clarifies this meaning:
So, both the original statement and the rewritten form using two “or” statements express the same logical concept: at least one of u or v must satisfy the condition related to V’, but not necessarily both.
https://g.co/gemini/share/5ca2bd4abb59
Albert Einstein Quote: “I want to know what God thinks. The rest are details.”
I rewrite another version after my interaction with the Google AI (Gemini):
https://www.preprints.org/manuscript/201908.0037/v10
In the previous version v10, we create two ways to prove that MWX2SAT is in P. In this version v11, we just remove the one that is flawed and keep the single one that is correct.
https://www.preprints.org/manuscript/201908.0037/v11
Dear Fellow,
I would be very grateful if you as an expert in the field would consider reviewing this publication:
Publication title: “Note for the P versus NP Problem”
https://www.scienceopen.com/document/read?id=94777eae-28c7-402d-8e6b-8e882de7a3f6
To review, go to that page and click on the “Review” button or consult the details about the reviewing process at ScienceOpen:
https://about.scienceopen.com/peer-review-guidelines
ScienceOpen enables every researcher to openly review any paper which has been submitted or published elsewhere.
Thank you very much also for your cooperation. I look forward to your review!
With kind regards,
Frank Vega
We improved the Lemma 1 (that is the polynomial time reduction from K-CLOSURE to MWX2SAT (Lemma 1)) and added a Discussion section with some important highlights in this last new version:
https://www.preprints.org/manuscript/201908.0037/v12
Dear Fellow,
I would be very grateful if you as an expert in the field would consider reviewing this publication:
Publication title: “Note for the P versus NP Problem” (Second Version)
https://www.scienceopen.com/document/read?vid=5e6e97ed-697f-4685-a43b-6c48e598af02
To review, go to that page and click on the “Review” button or consult the details about the reviewing process at ScienceOpen:
https://about.scienceopen.com/peer-review-guidelines
ScienceOpen enables every researcher to openly review any paper which has been submitted or published elsewhere.
Thank you very much also for your cooperation. I look forward to your review!
With kind regards,
Frank Vega
This the last version of the proof that P = NP:
https://www.techrxiv.org/users/258307/articles/716221-note-for-the-p-versus-np-problem
This version is as perfect as possible!
The problem with using Bitcoin in this value estimation is that none of the “value” of Bitcoin would actually be captured if the hashing algorithm were compromised. The price of Bitcoin would just become zero as everyone fanatically tries to shed their coins. The first person to notice their coins being stolen or the mining difficulty skyrocketing would sound the alarm and it’d be over before the attacker could cash out to fiat.
Yes, but we mean the present value of increasing the level of assurance that this scenario will not happen.