Ciro Santilli $$Sponsor Ciro$$ 中国独裁统治 China Dictatorship 新疆改造中心、六四事件、法轮功、郝海东、709大抓捕、2015巴拿马文件 邓家贵、低端人口、西藏骚乱

# Computer science

split "Computer" words: 2k
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:
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!

## Turing machine

split toc "Computer science" words: 133
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".
The smallest known Turing machine that cannot be proven to halt or not as of 2019 is 7,918-states: https://www.scottaaronson.com/blog/?p=2725. Shtetl-Optimized by Scott Aaronson is just the best website.
A bunch of non-reasonable-looking computers have also been proven to be Turing complete for fun, e.g. Magic: The Gathering.

### Universal Turing machine

split toc "Turing machine" words: 35
A Turing machine that simulates another Turing machine/input pair that has been encoded as a string.
In other words: an emulator!
The concept is fundamental to state several key results in computer science, notably the halting problem.

### Turing complete

split toc "Turing machine" words: 16
A computer model that is as powerful as the most powerful computer model we have: Turing machine!

## Formal language theory

split toc "Computer science" words: 213

### Recursively enumerable language

split toc "Formal language theory" words: 23
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.

### Recursive language

split toc "Formal language theory" words: 148

#### R (complexity)

split toc "Recursive language" words: 17
Set of all decision problems solvable by a Turing machine, i.e. that decide if a string belongs to a recursive language.

#### Undecidable problem

split toc "Recursive language" words: 116
Is a decision problem of determining if something belongs to a non-recursive 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.
Some undecidable problems are of recursively enumerable language, e.g. the halting problem.
Coolest ones besides the obvious boring halting problem:
##### Mortal matrix problem
split toc "Undecidable problem" words: 8
One of the most simple to state undecidable problems.
##### Computable problem
split toc "Undecidable problem" words: 13
A:
##### Computable number
split toc "Undecidable problem" words: 16
There are only boring exampes of taking an uncomputable language and converting it into a number?

#### Recursive set

split toc "Recursive language" words: 9
Same as recursive language but in the context of the integers.

### Chomsky hierarchy

split toc "Formal language theory" words: 42
This is the classic result of formal language theory, but there is too much slack between context free and context sensitive, which is PSPACE (larger than NP!).
TODO had seen a good table on Wikipedia with an expanded hierarchy, but lost it!

## Computational problem

split toc "Computer science" words: 947

### Decision problem

split toc "Computational problem" words: 49
computational problem where the solution is either yes or no.
When there are more than two possible answers, it is called a function problem.
Decision problems come up often in computer science because many important problems are often stated in terms of "decide if a given string belongs to given formal language".

#### Halting problem

split toc "Decision problem" words: 3
The canonical undecidable problem.

### Function problem

split toc "Computational problem" words: 316
A problem that has more than two possible yes/no outputs.
It is therefore a generalization of a decision problem.

#### Busy beaver ()

split toc "Function problem" words: 189
is the largest number of 1's written by a halting -state Turing machine.
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.

#### Integer factorization

split toc "Function problem" words: 97
Complexity: NP-intermediate as of 2020:
The basis of RSA: RSA. But not proved NP-complete, which leads to:
##### NP-hard cryptosystems
split toc "Integer factorization" words: 47
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?

#### Discrete logarithm

split toc "Function problem" words: 12
NP-intermediate as of 2020 for similar reasons as integer factorization.

### Algorithm

split toc "Computational problem" words: 165
A solution to a computational problem!

#### Algorithm cheatsheet

split toc "Algorithm" words: 10
Draft by Ciro Santilli with cross language input/output test cases: https://github.com/cirosantilli/algorithm-cheat
By others:

#### Data structure

split toc "Algorithm" words: 150
##### Associative array (map, dictionary)
split toc "Data structure" words: 8
More commonly known as a map or dictionary.
##### Tree (data-structure)
split toc "Data structure" words: 142
###### Tree traversal
split toc "Tree" words: 142
Like breadth-first search, this also has the property of visiting parents before any children.
###### Interative pre-order
split toc "Pre-order depth-first search" words: 19
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 unlike pre-order depth-first search and post-order depth-first search which generalize obviously to general trees.
###### Interative in-order
split toc "In-order depth-first search" words: 57
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:
• (ELSE) pop
• visit
• if there is right
• move right
• GOTO START
• else:
• GOTO ELSE
The control flow can be slightly simplified if we allow NULLs: https://www.geeksforgeeks.org/inorder-tree-traversal-without-recursion/
###### Post-order depth-first search (LRN)
split toc "Depth-first search" words: 19
Has the property of visiting all children before the parent.
###### Interative post-order
This is the hardest one to do iteratively.

### Complexity class

split toc "Computational problem" words: 345

#### Big O notation family

split toc "Complexity class" words: 149
This is a family of notations related to the big O notation. A good mnemonic summary of all notations would be:
##### Big O notation ()
split toc "Big O notation family" words: 69
Module bound above, possibly multiplied by a constant: $$f(x)=O(g(x)) (1)$$ is defined as: $$∃M>0∃x0​∀x>x0​:∣f(x)∣≤Mg(x) (2)$$
E.g.:
• . For , is enough. Otherwise, any will do, the bottom line will always catch up to the top one eventually.
##### Little-o notation ()
split toc "Big O notation family" words: 53
Stronger version of the big O notation, basically means that ratio goes to zero. In big O notation, the ratio does not need to go to zero.
So in informal terms, big O notation means , and little-o notation means .
E.g.:
• K does not tend to zero

#### NP (complexity)

split toc "Complexity class" words: 196
##### NP-complete
split toc "NP" words: 39
A problem that is both NP and NP-hard.
###### P versus NP problem (P vs NP)
split toc "NP-complete" words: 32
Interesting because of the Cook-Levin theorem: if only a single NP-complete problem were in P, then all NP-complete problems would also be P!
We all know the answer for this: either false or independent.
##### NP-hard
split toc "NP" words: 15
A problem such that all NP problems can be reduced in polynomial time to it.
##### NP-intermediate
split toc "NP" words: 130
This is the most interesting class of problems for BQP as we haven't proven that they are neither:
• P: would be boring on quantum computer
• NP-complete: would likely be impossible on a quantum computer
###### BQP
split toc "NP-intermediate" words: 95
• 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!
##### Co-NP
split toc "NP" words: 5

### Optimization problem

split toc "Computational problem" words: 70

#### Logistics

split toc "Optimization problem" words: 63
##### Last mile problem
split toc "Logistics" words: 63
The exact same problem appears over and over, e.g.:
• transportaion: the last mile of the trip when everyone leaves the train and goes to their different respective offices is the most expensive
• telecommunications: the last mile of wire linking local hubs to actual homes is the most expensive
• electrical grid: same as telecommunications
Ciro Santilli also identified knowledge version of this problem: the missing link between basic and advanced.

#### Value function

split toc "Optimization problem" words: 7
The function being maximized in a optimization problem.

## Cryptography

split toc "Computer science" words: 619

## Hash function

split toc "Computer science" words: 52
Applications: