Incoming links: P versus NP problem
P for quantum computing!
Heck, we know nothing about this class yet related to non quantum classes!
- conjectured not to intersect with NP-complete, because if it were, all NP-complete problems could be solved efficiently on quantum computers, and none has been found so far as of 2020.
- conjectured to be larger than P, but we don't have a single algorithm provenly there:
- it is believed that the NP complete ones can't be solved
- if they were neither NP-complete nor P, it would imply P != NP
- we just don't know if it is even contained inside NP!
A branch of mathematics that attempts to prove stuff about computers.
Unfortunately, all software engineers already know the answer to the useful theorems though (except perhaps notably for cryptography), e.g. all programmers obviously know that iehter P != NP or that this is unprovable or some other "for all practical purposes practice P != NP", even though they don't have proof.
And 99% of their time, software engineers are not dealing with mathematically formulatable problems anyways, which is sad.
The only useful "computer science" subset every programmer ever needs to know is:
- for arrays: dynamic array vs linked list
- for associative array: binary search tree vs hash table. See also Heap vs Binary Search Tree (BST). No need to understand the algorithmic details of the hash function, the NSA has already done that for you.
- don't use Bubble sort for sorting
- you can't parse HTML with regular expressions: stackoverflow.com/questions/1732348/regex-match-open-tags-except-xhtml-self-contained-tags/1732454#1732454 because of formal language theory
Funnily, due to the formalization of mathematics, mathematics can be seen as a branch of computer science, just like computer science can be seen as a branch of Mathematics!
Ciro Santilli would like to fully understand the statements and motivations of each the problems!
Easy to understand the motivation:
- Navier-Stokes existence and smoothness is basically the only problem that is really easy to understand the statement and motivation :-)
- p versus NP problem
Hard to understand the motivation!
- Riemann hypothesis: a bunch of results on prime numbers, and therefore possible applications to cryptographyOf course, everything of interest has already been proved conditionally on it, and the likely "true" result will in itself not have any immediate applications.As is often the case, the only usefulness would be possible new ideas from the proof technique, and people being more willing to prove stuff based on it without the risk of the hypothesis being false.
- Yang-Mills existence and mass gap: this one has to do with finding/proving the existence of a more decent formalization of quantum field theory that does not resort to tricks like perturbation theory and effective field theory with a random cutoff valueThis is important because the best theory of light and electrons (and therefore chemistry and material science) that we have today, quantum electrodynamics, is a quantum field theory.