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!

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.

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.

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.

Set of all decision problems solvable by a Turing machine, i.e. that decide if a string belongs to a recursive language.

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
- Diophantine equation existence of solutions: undecidable Diophantine equation problems

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.

A:

- decidable problem is to a decision problem
- like a computable problem is to a function problem

There are only boring exampes of taking an uncomputable language and converting it into a number?

Same as recursive language but in the context of the integers.

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!).

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.

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".

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:

- Goldbach's conjecture: 27 states
- Riemann hypothesis: 744 states
- the consistency of Zermelo-Fraenkel set theory: 7910 states

Therefore, if we were able to compute $BB(n)$, we would be able to prove those conjectures automatically, by letting the machine run up to $BB(n)$, and if it hadn't halted by then, we would know that it would never halt.

Of course, in practice, $BB$ 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: 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?

The basis of RSA: RSA. But not proved NP-complete, which leads to:

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?

- 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?"

NP-intermediate as of 2020 for similar reasons as integer factorization.

A solution to a computational problem!

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

By others:

More commonly known as a map or dictionary.

This is a family of notations related to the big O notation. A good mnemonic summary of all notations would be:

- big O notation: $∣f∣≤g$
- little-o notation: $∣f∣<g$

E.g.:

- $∀c∈Rx+c=O(x)$. For $c<0$, $M=1$ is enough. Otherwise, any $M>1$ will do, the bottom line will always catch up to the top one eventually.

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.

E.g.:

- $x=O(x)$
- $x =o(x)$K does not tend to zero
- $x=O(x_{2})$
- $x=o(x_{2})$

Strictly speaking, only defined for decision problems: cs.stackexchange.com/questions/9664/is-it-necessary-for-np-problems-to-be-decision-problems/128702#128702

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.

A problem such that all NP problems can be reduced in polynomial time to it.

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

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!

- math.stackexchange.com/questions/361422/why-isnt-np-conp "Why isn't NP = coNP?"
- stackoverflow.com/questions/17046440/whats-the-difference-between-np-and-co-np
- cs.stackexchange.com/questions/9795/is-the-open-question-np-co-np-the-same-as-p-np
- mathoverflow.net/questions/31821/problems-known-to-be-in-both-np-and-conp-but-not-known-to-be-in-p

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.

The function being maximized in a optimization problem.

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

Applications:

- 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: security.blogoverflow.com/2013/09/about-secure-password-hashing/