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

# Computer science

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 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: 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 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 words: 16
A computer model that is as powerful as the most powerful computer model we have: Turing machine!

## Formal language theory

split words: 240

### Recursively enumerable language

split 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 words: 175

#### R (complexity)

split 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 words: 143
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 words: 35
One of the most simple to state undecidable problems.
The reason that it is undecidable is that you can repeat each matrix any number of times, so there isn't a finite number of possibilities to check.
split words: 13
A:
##### Computable number
split words: 16
There are only boring exampes of taking an uncomputable language and converting it into a number?

#### Recursive set

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

### Chomsky hierarchy

split 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 words: 826

### Decision problem

split 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 words: 3
The canonical undecidable problem.

### Function problem

split 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 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 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 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 words: 12
NP-intermediate as of 2020 for similar reasons as integer factorization.

### Algorithm

split words: 23
A solution to a computational problem!

#### Algorithm cheatsheet

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

#### Data structure

split words: 8
##### Associative array (map, dictionary)
split words: 8
More commonly known as a map or dictionary.

### Complexity class

split words: 345

#### Big O notation family

split 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 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 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 words: 196
##### NP-complete
split words: 39
A problem that is both NP and NP-hard.
###### P versus NP problem (P vs NP)
split 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 words: 15
A problem such that all NP problems can be reduced in polynomial time to it.
##### NP-intermediate
split 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 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!
split words: 5

### Optimization problem

split words: 70

#### Logistics

split words: 63
##### Last mile problem
split 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 words: 7
The function being maximized in a optimization problem.

### List of computational problems

split words: 21

#### 3SUM

split words: 21
It is cool how even for such a "simple looking" problem, we were still unable to prove optimality as of 2020.

split words: 633

split words: 52
Applications: