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: https://stackoverflow.com/questions/1732348/regex-match-open-tags-except-xhtml-self-contained-tags/1732454#1732454 because of formal language theory
The dominating model of a computer.
The model is extremely simple, but has been proven to be able to solve all the problems that any reasonable computer model can solve, thus its adoption as the "default model".
A bunch of non-reasonable-looking computers have also been proven to be Turing complete for fun, e.g. Magic: The Gathering.
A Turing machine that simulates another Turing machine/input pair that has been encoded as a string.
In other words: an emulator!
A computer model that is as powerful as the most powerful computer model we have: Turing machine!
There is a Turing machine that halts for every member of the language with the answer yes, but does not necessarily halt for non-members.
Subset of recursively enumerable language as explained at: difference between recursive language and recursively enumerable language.
Or in other words: there is no Turing machine that always halts for every input with the yes/no output.
Every undecidable problem must obviously have an infinite number of "possibilities of stuff you can try": if there is only a finite number, then you can brute-force it.
One of the most simple to state undecidable problems.
There are only boring exampes of taking an uncomputable language and converting it into a number?
By Noam Chomsky.
TODO had seen a good table on Wikipedia with an expanded hierarchy, but lost it!
computational problem where the solution is either yes or no.
When there are more than two possible answers, it is called a function problem.
The canonical undecidable problem.
A problem that has more than two possible yes/no outputs.
It is therefore a generalization of a decision problem.
Some variant definitions define it as the number of time steps taken by the machine instead. Wikipedia talks about their relationship, but no patience right now.
This problem is theoretically interesting because many important mathematical conjectures have been proved to be equivalent to whether a given Turing machine halts or not, this is notably the case for:
Therefore, if we were able to compute , we would be able to prove those conjectures automatically, by letting the machine run up to , and if it hadn't halted by then, we would know that it would never halt.
Of course, in practice, is generally uncomputable, so we will never know it. And furthermore, even if it were, it would take a lot longer than the age of the universe to compute any of it, so it would be useless.
However, philosophically speaking at least, the number of states of the equivalent Turing machine gives us a philosophical idea of the complexity of the problem.
Complexity: NP-intermediate as of 2020:
- expected not to be NP-complete because it would imply NP != Co-NP: https://cstheory.stackexchange.com/questions/167/what-are-the-consequences-of-factoring-being-np-complete#comment104849_169
- expected not to be in P because "could we be that dumb that we haven't found a solution after having tried for that long?
This is natural question because both integer factorization and discrete logarithm are the basis for the most popular public-key cryptography systems as of 2020 (RSA and Diffie-Hellman key exchange respectively), and both are NP-intermediate. Why not use something more provenly hard?
- https://cs.stackexchange.com/questions/356/why-hasnt-there-been-an-encryption-algorithm-that-is-based-on-the-known-np-hard "Why hasn't there been an encryption algorithm that is based on the known NP-Hard problems?"
A solution to a computational problem!
More commonly known as a map or dictionary.
Like breadth-first search, this also has the property of visiting parents before any children.
This is the easiest one to do iteratively:
- pop and visit
- push right to stack
- push left to stack
Only makes sense for binary tree because if there are more nodes it is not clear what the top node should go in the middle of.
This is a bit harder than interative pre-order: now we have to check if there is a left or right element or not:
- (START) push current
- if there is left:
- move left
- (ELSE) pop
- if there is right
- move right
- GOTO START
- GOTO ELSE
The control flow can be slightly simplified if we allow NULLs: https://www.geeksforgeeks.org/inorder-tree-traversal-without-recursion/
Has the property of visiting all children before the parent.
This is the hardest one to do iteratively.
- . For , is enough. Otherwise, any will do, the bottom line will always catch up to the top one eventually.
- K does not tend to zero
Strictly speaking, only defined for decision problems: https://cs.stackexchange.com/questions/9664/is-it-necessary-for-np-problems-to-be-decision-problems/128702#128702
We all know the answer for this: either false or independent.
A problem such that all NP problems can be reduced in polynomial time to it.
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!
- https://math.stackexchange.com/questions/361422/why-isnt-np-conp "Why isn't NP = coNP?"
The exact same problem appears over and over, e.g.:
The function being maximized in a optimization problem.
- hash map which is a O(1) amortized implementation of a map
- creating unbreakable chains of data, e.g. for Git commits or Bitcoin.
- storing passwords on a server in a way that if the password database is stolen, attackers can't reuse them on other websites where the user used the same password: https://security.blogoverflow.com/2013/09/about-secure-password-hashing/