), 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: vs
* for : vs . See also https://stackoverflow.com/questions/6147242/heap-vs-binary-search-tree-bst/29548834#29548834[Heap vs Binary Search Tree (BST)]. No need to understand the algorithmic details of the hash function, the has already done that for you.
* don't use https://en.wikipedia.org/wiki/Bubble_sort[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
Funnily, due to the , can be seen as a branch of computer science, just like computer science can be seen as a branch of Mathematics!
= Turing machine
{c}
{parent=Computer science}
{wiki}
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[]. https://www.scottaaronson.com/[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. .
= Universal Turing machine
{c}
{parent=Turing machine}
{wiki}
A Turing machine that simulates another Turing machine/input pair that has been encoded as a string.
In other words: an !
The concept is fundamental to state several key results in , notably the .
= Turing complete
{c}
{parent=Turing machine}
{wiki=Turing_completeness}
A computer model that is as powerful as the most powerful computer model we have: !
= Formal language theory
{parent=Computer science}
= Formal language
{parent=Formal language theory}
{wiki}
= Abstract syntax tree
{parent=Formal language}
{title2=AST}
{wiki}
= Recursively enumerable language
{parent=Formal language theory}
{tag=Chomsky hierarchy}
{wiki}
There is a that halts for every member of the language with the answer yes, but does not necessarily halt for non-members.
Non-examples: https://cs.stackexchange.com/questions/52503/non-recursively-enumerable-languages
= RE
{disambiguate=complexity}
{parent=Recursively enumerable language}
{wiki}
= Recursive language
{parent=Formal language theory}
{tag=Recursively enumerable language}
{wiki}
Subset of as explained at: .
= R
{disambiguate=complexity}
{parent=Recursive language}
{wiki}
Set of all solvable by a , i.e. that decide if a string belongs to a .
= Undecidable problem
{parent=Recursive language}
{tag=Decision problem}
{wiki}
= Undecidable
{synonym}
Is a of determining if something belongs to a non-.
Or in other words: there is no 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 , e.g. the .
Lists of undecidable problems.
* https://mathoverflow.net/questions/11540/what-are-the-most-attractive-turing-undecidable-problems-in-mathematics
* https://en.wikipedia.org/wiki/List_of_undecidable_problems
Coolest ones besides the obvious boring :
*
* existence of solutions:
= Undecidability requires infinitely many inputs
{parent=Undecidable problem}
If there are infinitely many inputs, we can always construct a (potentially exponentially huge) that hardcodes the outcome for every possible input, so the problem is never .
The problem is of course deciding and proving the outcome for each possible input, notably as it is possible that calculation for some of the inputs may be from .
= Mortal matrix problem
{parent=Undecidable problem}
https://en.wikipedia.org/wiki/Zero_matrix#Occurrences
One of the most simple to state .
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.
= Computable problem
{parent=Undecidable problem}
{wiki}
= Uncomputable problem
{synonym}
= Computable
{synonym}
= Uncomputable
{synonym}
= Uncomputability
{synonym}
A:
* [decidable problem] is to a
* like a computable problem is to a
= Computable function
{parent=Undecidable problem}
{wiki}
= Uncomputable function
{parent=Computable function}
The prototypical example is the , which is the easiest example to reach from the .
= Computable number
{parent=Undecidable problem}
{wiki}
= Uncomputable number
{synonym}
https://math.stackexchange.com/questions/462790/are-there-any-examples-of-non-computable-real-numbers
There are only boring exampes of taking an uncomputable language and converting it into a number?
= Difference between recursive language and recursively enumerable language
{parent=Recursive language}
{wiki}
https://stackoverflow.com/questions/33467040/what-is-the-difference-between-recursive-and-recursively-enumerable-languages/65455863#65455863
= Recursive set
{parent=Recursive language}
{wiki}
Same as but in the context of the .
= Chomsky hierarchy
{c}
{parent=Formal language theory}
{wiki}
This is the classic result of , but there is too much slack between context free and context sensitive, which is PSPACE (larger than !).
By .
TODO had seen a good table on Wikipedia with an expanded hierarchy, but lost it!
= Regular language
{parent=Chomsky hierarchy}
{wiki}
= Regular expression
{parent=Regular language}
{wiki}
= Computational problem
{parent=Computer science}
{wiki}
The list: https://complexityzoo.uwaterloo.ca/Complexity_Zoo
= Decision problem
{parent=Computational problem}
{wiki}
where the solution is either yes or no.
When there are more than two possible answers, it is called a .
Decision problems come up often in because many important problems are often stated in terms of "decide if a given string belongs to given ".
= Halting problem
{parent=Decision problem}
{tag=Undecidable problem}
{wiki}
The canonical .
= Turing machine decider
{c}
{parent=Halting problem}
A decider is a program that decides if one or more halts of not.
Of course, because what we know about the , there cannot exist a single decider that decies all .
E.g. has a set of deciders clearly published, which decide a large part of . Their proposed deciders are listed at: https://discuss.bbchallenge.org/c/deciders/5[] and actually applied ones at: https://bbchallenge.org[].
But there are deciders that can decide large classes of turing machines.
Many (all/most?) deciders are based on simulation of machines with arbitrary cutoff , e.g. the cutoff space/time of a .
The simplest and most obvious example is the
= Turing machine regex tape notation
{c}
{parent=Turing machine decider}
is 's made up name for the notation used e.g. at:
* https://www.sligocki.com/2023/02/02/skelet-34.html
* https://www.sligocki.com/2022/06/10/ctl.html
Most of it is just regular notation, with a few differences:
* $0^{\inf}$ denotes the right or left edge of the (zero initialized) tape. It is often omitted as we always just assume it is always present on both sides of every regex
* `A`, `B`, `C`, `D` and `E` denotes the current machine state. This is especially common notation in the context of the problem
* `<` and `>` next to the state indicate if the head is on top of the left or right element. E.g.:
``
11 (01)^n tape and extract higher level patterns from them, which is how you go about understanding a Turing machin in order to apply .
= Cycler Turing machine
{parent=Turing machine decider}
= Turing machine cycler decider
{c}
{synonym}
Bibliography: https://discuss.bbchallenge.org/t/decider-cyclers/33[]
Example: https://bbchallenge.org/279081[].
These are very simple, they just check for exact state repetitions, which obviously imply that they will run forever.
Unfortunately, cyclers may need to run throun an initial setup phase before reaching the initial cycle point, which is not very elegant.
Also, we have no way of knowing the initial setup length of the actual cycle length, so we just need an arbitrary cutoff value.
And unfortunatly, this can lead to misses, e.g. , a 5 state machine, has a (translated) cycle that starts at around 50-200M styeps, and takes 8 trillion steps to repeat.
= Translated cycler Turing machine
{parent=Turing machine decider}
Bibliography: https://discuss.bbchallenge.org/t/decider-translated-cyclers/34
Like a cycler, but the cycle starts at an offset.
To see infinity, we check that if the machine only goes left N squares until reaching the repetition, then repetition must only be N squares long.
= Closed Tape Language decider
{parent=Turing machine decider}
Described at: https://www.sligocki.com/2022/06/10/ctl.html
= Busy beaver
{parent=Halting problem}
{tag=Function problem}
{wiki}
= Busy beaver game
{synonym}
The busy beaver game consists in finding, for a given $n$, the turing machine with $n$ states that writes the largest possible number of 1's on a tape initially filled with 0's. In other words, computing the for a given $n$.
There are only finitely many Turing machines with $n$ states, so we are certain that there exists such a maxium. Computing the for a given $n$ then comes down to solving the halting problem for every single machine with $n$ states.
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.
The Busy Beaver problem is cool because it puts the in a more precise numerical light, e.g.:
* the is the most obvious one can come up with starting from the
* the allows us to gauge the difficulty of proving certain (yet unproven!) mathematical
Bibliography:
* https://www.scottaaronson.com/blog/?p=4916
* https://www.quantamagazine.org/the-busy-beaver-game-illuminates-the-fundamental-limits-of-math-20201210
= Step busy beaver
{parent=Busy beaver}
The is a variant of the counts the number of steps before halt, instead of the number of 1's written to the tape.
As of 2023, it appears that the same machine, , will win both for 5 states. But this is not always necessarily the case.
= Busy beaver function
{parent=Busy beaver}
{tag=Uncomputable function}
{title2=$BB(n)$}
$BB(n)$ is the largest number of 1's written by a [halting] $n$-state on a tape initially filled with 0's.
\Video[https://www.youtube.com/watch?v=kmAc1nDizu0]
{title=The Boundary of Computation by Mutual Information (2023)}
= Specific values of the Busy beaver function
{parent=Busy beaver function}
The following things come to mind when you look into research in this area, especially the search for which was hard but doable:
* it is largely , i.e. done by non-professionals, a bit like the . Humbly, they tend to call their results [lemmas]
* complex structure emerges from simple rules, leading to a complex with a few edge cases, much like the
Bibliography:
* https://cs.stackexchange.com/questions/59344/what-are-very-short-programs-with-unknown-halting-status
* https://cs.stackexchange.com/questions/44869/what-are-the-simplest-examples-of-programs-that-we-do-not-know-whether-they-term imprecise duplicate
* https://cstheory.stackexchange.com/questions/20978/what-is-the-smallest-turing-machine-where-it-is-unknown-if-it-halts-or-not
= Turing machine acceleration
{c}
{parent=Specific values of the Busy beaver function}
refers to using high level understanding of specific properties of specific Turing machines to be able to simulate them much fatser than naively running the simulation as usual.
Acceleration allows one to use simulation to find infinite loops that might be very long, and would not be otherwise spotted without acceleration.
This is for example the case of https://www.sligocki.com/2023/03/13/skelet-1-infinite.html proof of .
= Busy Beaver Challenge
{c}
{parent=Specific values of the Busy beaver function}
= The Busy Beaver Challenge
{synonym}
https://bbchallenge.org/story
Project trying to compute once and for all. Notably it has better presentation and organization than any other previous effort, and appears to have grouped everyone who cares about the topic as of the early 2020s.
Very cool initiative!
By 2023, they had basically decided every machine: https://discuss.bbchallenge.org/t/the-30-to-34-ctl-holdouts-from-bb-5/141
In June 2024 they felt that they had verified the result after a full proof was published:
* https://www.quantamagazine.org/amateur-mathematicians-find-fifth-busy-beaver-turing-machine-20240702/
* https://discuss.bbchallenge.org/t/july-2nd-2024-we-have-proved-bb-5-47-176-870/237
So now onto I guess.
= BB(5)
{c}
{parent=Specific values of the Busy beaver function}
= Busy beaver function of 5
{synonym}
{title2}
The last value we will likely every know for the ! is likely completely out of reach forever.
By 2023, it had basically been decided by the as mentioned at: https://discuss.bbchallenge.org/t/the-30-to-34-ctl-holdouts-from-bb-5/141[], pending only further verification. It is going to be one of those highly computational proofs that will be needed to be for people to finally settle.
As that project beautifully puts it, as of 2023 prior to full resolution, this can be considered the:
\Q[simplest open problem in mathematics]
on the .
= Marxen-Buntrock machine
{parent=BB(5)}
{title2=1989}
{title2=4098 1's}
{title2=~47M steps}
Best machine known since 1989 as of 2023, before a full proof of all 5 state machines had been carried out.
Entry on : https://bbchallenge.org/1RB1LC_1RC1RB_1RD0LE_1LA1LD_1RZ0LA
Paper extracted to HTML by Heiner Marxen: http://turbotm.de/~heiner/BB/mabu90.html
= Skelet’s machines
{c}
{parent=BB(5)}
{title2=2003}
List on : https://bbchallenge.org/skelet
Bibliography:
* https://bbchallenge.org/story#skelets-43-undecided-machines
* https://skelet.ludost.net/bb/nreg.html
= Skelet machine \#1
{c}
{parent=Skelet’s machines}
{tag=Translated cycler Turing machine}
{title2=proved 2023}
{title2=cyclel start: 50-200M}
{title2=period: ~8B}
On : https://bbchallenge.org/68329601
= Skelet machine \#1 is infinite
{c}
{parent=Skelet machine \#1}
Non formal proof with a program March 2023: https://www.sligocki.com/2023/03/13/skelet-1-infinite.html Awesome article that describes the proof procedure.
August 2023: https://discuss.bbchallenge.org/t/skelet-1-is-a-translated-cycler-coq-agrees/166
The proof uses to show that is a with humongous cycle paramters:
* start between 50-200 M steps, not calculated precisely on the original post
* period: ~8 billion steps
= BB(6)
{c}
{parent=Specific values of the Busy beaver function}
= Busy beaver function of 6
{synonym}
{title2}
= BB(6) is hard
{c}
{parent=BB(6)}
https://wiki.bbchallenge.org/wiki/Antihydra[]:
* https://news.ycombinator.com/item?id=40864949 BB(6), The 6th Busy Beaver Number, is harder than a Collatz-like math problem
* https://www.reddit.com/r/math/comments/1dubva0/finding_the_6th_busy_beaver_number_%CF%836_aka_bb6_is/ "Finding the 6th busy beaver number (Σ(6), AKA BB(6)) is at least as hard as a hard Collatz-like math problem called Antihydra":
* https://www.reddit.com/r/compsci/comments/1duc62e/finding_the_6th_busy_beaver_number_%CF%836_aka_bb6_is/
= Antihydra
{parent=BB(6) is hard}
{title2=28 Jun 2024}
https://wiki.bbchallenge.org/wiki/Antihydra
= Antihydra GMP implementation
{parent=Antihydra}
{tag=GNU Multiple Precision Arithmetic Library}
= gmp/antihydra.c
{file}
{parent=Antihydra}
{tag=GMP example}
Also posted at:
* https://wiki.bbchallenge.org/wiki/Antihydra
* https://cstheory.stackexchange.com/questions/20978/what-is-the-smallest-turing-machine-where-it-is-unknown-if-it-halts-or-not/53326#53326
* https://cs.stackexchange.com/questions/59344/what-are-very-short-programs-with-unknown-halting-status/162108#162108
= Busy beaver scale
{parent=Busy beaver}
The allows us to gauge the difficulty of proving certain (yet unproven!) mathematical !
To to this, people have reduced certain mathematical problems to deciding the of a specific .
A good example is perhaps the . We just make a that successively checks for each even number of it is a sum of two primes by naively looping down and trying every possible pair. Let the machine halt if the check fails. So this machine halts the is false! See also .
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 , so we will never know it. And furthermore, even if it were computable, 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 gives us a philosophical idea of the complexity of the problem.
The is likely mostly useless, since we are able to prove that many non-trivial do halt, often by reducing problems to simpler known cases. But still, it is cute.
But maybe, just maybe, reduction to Turing machine form could be useful. E.g. and other attempts to solve have come up with large number of automated (usually parametrized up to a certain threshold) programs that automatically determine if certain (often large numbers of) Turing machines run forever.
So it it not impossible that after some reduction to a standard form, some conjecture just gets automatically brute-forced by one of the deciders, this is a path to
= Turing machine compiler
{c}
{parent=Busy beaver scale}
https://cs.stackexchange.com/questions/50815/compiler-that-compiles-to-a-turing-machine/161872#161872
= Automated theorem proving by halting problem reduction
{parent=Busy beaver scale}
{tag=Automated theorem proving}
If you can reduce a mathematical problem to the of a specific turing machine, as in the case of a few machines of the , then using could serve as a method of .
That feels like it could be an elegant proof method, as you reduce your problem to one of the most well studied representations that exists: a .
However it also appears that certain problems cannot be reduced to a ... OMG life sucks (or is awesome?): {full}.
= Conjecture reduction to a halting problem
{c}
{parent=Automated theorem proving by halting problem reduction}
https://bbchallenge.org/story#what-is-known-about-bb lists some (all?) cool examples,
* BB(15): , which has some relation to
* BB(27):
* BB(744):
* BB(748): from the
* BB(7910): from the
https://wiki.bbchallenge.org/wiki/Cryptids contains a larger list. In June 2024 it was discovered that .
= Turing machine that halts if and only if the Goldbach conjecture is false
{c}
{parent=Conjecture reduction to a halting problem}
{tag=Goldbach conjecture}
{title2=27-state}
https://www.scottaaronson.com/papers/bb.pdf
= Turing machine that halts if and only if Collatz conjecture is false
{c}
{parent=Conjecture reduction to a halting problem}
{tag=Collatz conjecture}
https://mathoverflow.net/questions/309044/is-there-a-known-turing-machine-which-halts-if-and-only-if-the-collatz-conjectur suggests one does not exist. Amazing.
Intuitively we see that the situation is fundamentally different from the because for Collatz the counter example must go off into infinity, while in Goldbach conjecture we can finitely check any failures.
Amazing.
= Function problem
{parent=Computational problem}
{wiki}
A problem that has more than two possible yes/no outputs.
It is therefore a generalization of a .
= Integer multiplication
{parent=Function problem}
https://cs.stackexchange.com/questions/16226/what-is-the-fastest-algorithm-for-multiplication-of-two-n-digit-numbers
= Integer factorization
{parent=Function problem}
{wiki}
Complexity: as of 2020:
* expected not to be because it would imply NP != : https://cstheory.stackexchange.com/questions/167/what-are-the-consequences-of-factoring-being-np-complete#comment104849_169
* expected not to be in

because "could we be that dumb that we haven't found a solution after having tried for that long?
The basis of RSA: . But not proved , which leads to:
= Integer factorization algorithm
{parent=Integer factorization}
= NP-hard cryptosystems
{c}
{parent=Integer factorization}
This is natural question because both and are the basis for the most popular systems as of 2020 ( and respectively), and both are . 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?"
= Discrete logarithm
{parent=Function problem}
{wiki}
of a [groups].
as of 2020 for similar reasons as .
An important case is the in which the group is a .
= Discrete logarithm of the cyclic group
{parent=Discrete logarithm}
This is the problem where the group is a .
In this case, the problem becomes equivalent to reversing .
This computational problem forms the basis for , because can be efficiently computed, but no known way exists to efficiently compute the reverse function.
= Algorithm
{parent=Computational problem}
{wiki}
A solution to a !
= Algorithm cheatsheet
{parent=Algorithm}
Draft by with cross language input/output test cases: https://github.com/cirosantilli/algorithm-cheat
By others:
* https://github.com/TheAlgorithms/Python
= Data structure
{parent=Algorithm}
{wiki}
= Associative array
{parent=Data structure}
{title2=map}
{title2=dictionary}
{wiki}
More commonly known as a map or dictionary.
= Binary search tree
{parent=Associative array}
{title2=BST}
{tag=Binary tree}
{tag=Ordered tree}
{wiki}
= B-tree
{c}
{parent=Binary search tree}
Like , but each node can have multiple objects and more than two children.
\Image[https://upload.wikimedia.org/wikipedia/commons/thumb/6/65/B-tree.svg/799px-B-tree.svg.png]
= Hash table
{parent=Associative array}
{wiki}
= Hash map
{synonym}
{title2}
= Dynamic array
{parent=Data structure}
{wiki}
= Linked list
{parent=Data structure}
{wiki}
= Recursion
{disambiguate=computer science}
{parent=Algorithm}
{wiki}
= Recursion
{synonym}
= Recursive algorithm
{synonym}
= Iteration
{parent=Recursion (computer science)}
{wiki}
= Iterative algorithm
{parent=Iteration}
{wiki}
= Sorting algorithm
{parent=Algorithm}
{wiki}
= String-sorting algorithm
{parent=Sorting algorithm}
= Natural sort order
{parent=String-sorting algorithm}
{wiki}
= String-search algorithm
{parent=Algorithm}
{wiki}
= Complexity class
{parent=Computational problem}
{wiki}
= Complexity
{synonym}
= Time complexity
{parent=Complexity class}
{wiki}
= Quasilinear time
{parent=Time complexity}
{title2=$O(n \log^k(n))$}
{wiki}
= Big O notation family
{parent=Complexity class}
This is a family of notations related to the . A good mnemonic summary of all notations would be:
* : $|f| \le g$
* : $|f| \lt g$
= Big O notation
{parent=Big O notation family}
{title2=$O(n)$}
{wiki}
Module bound above, possibly multiplied by a constant:
$$
f(x) = O(g(x))
$$
is defined as:
$$
\exists M > 0 \exists x_0 \forall x > x_0 \colon |f(x)| \leq M g(x)
$$
E.g.:
* $\forall c \in \R x + 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.
= Little-o notation
{parent=Big O notation family}
{title2=$o(n)$}
Stronger version of the , basically means that ratio goes to zero. In , the ratio does not need to go to zero.
So in informal terms, means $\leq$, and means $<$.
E.g.:
* $x = O(x)$
* $x \ne o(x)$K does not tend to zero
* $x = O(x^2)$
* $x = o(x^2)$
= Primitive recursive function
{parent=Complexity class}
{wiki}
= Primitive recursive
{synonym}
In intuitive terms it consists of all integer functions, possibly with multiple input arguments, that can be written only with a sequence of:
* variable assignments
* addition and subtraction
* integer comparisons and if/else
*
``
for (i = 0; i < n; i++)
``
and such that `n` does not change inside the loop body, i.e. no with arbitrary conditions.
`n` does not have to be a constant, it may come from previous calculations. But it must not change inside the loop body.
basically include every integer function that comes up in practice. Primitive recursive functions can have huge complexity, and it strictly contains . As such, they mostly only come up in contexts.
The cool thing about is that the number of iterations is always bound, so we are certain that they terminate and are therefore .
This also means that there are necessarily functions which are not , as we know that there must exist functions, e.g. the .
Adding unbounded of course enables us to simulate arbitrary , and therefore increases the .
More finely, there are , e.g. most famously the .
= Non-primitive total recursive function
{parent=Primitive recursive function}
= Ackermann function
{c}
{parent=Non-primitive total recursive function}
{wiki}
To get an intuition for it, see the sample computation at: https://en.wikipedia.org/w/index.php?title=Ackermann_function&oldid=1170238965#TRS,_based_on_2-ary_function where $S(n) = n + 1$ in this context. From this, we immediately get the intuition that these functions are recursive somehow.
= Galactic algorithm
{parent=Complexity class}
{wiki}
= ELEMENTARY
{c}
{disambiguate=complexity}
{parent=Complexity class}
{title2=$2^n$, $2^{2^n}$, ...}
{wiki=EXPTIME}
= EXPTIME
{c}
{parent=ELEMENTARY (complexity)}
{wiki}
= NP
{c}
{disambiguate=complexity}
{parent=EXPTIME}
{wiki}
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
= P
{c}
{disambiguate=complexity}
{parent=NP (complexity)}
{wiki}
= Polynomial time
{synonym}
{title2}
= Polynomial time algorithm
{parent=P (complexity)}
= NP-complete
{c}
{parent=NP (complexity)}
{wiki=NP-completeness}
A problem that is both and .
= Cook-Levin theorem
{c}
{parent=NP-complete}
{wiki=Cook–Levin_theorem}
= P versus NP problem
{parent=NP-complete}
{wiki}
= P vs NP
{c}
{synonym}
{title2}
Interesting because of the : if only a single problem were in

, then all NP-complete problems would also be P!
We all know the answer for this: either false or .
= Ladner's Theorem
{c}
{parent=P versus NP problem}
= NP-hard
{c}
{parent=NP (complexity)}
{wiki=NP-hardness}
A problem such that all NP problems can be reduced in polynomial time to it.
= NP-intermediate
{c}
{parent=NP (complexity)}
{wiki}
This is the most interesting class of problems for as we haven't proven that they are neither:
*

: would be boring on quantum computer
* : would likely be impossible on a quantum computer
Big list: https://cstheory.stackexchange.com/questions/79/problems-between-p-and-npc/460#460
= BQP
{c}
{parent=NP-intermediate}
{wiki}

for !
Heck, we know nothing about this class yet related to non quantum classes!
* conjectured not to intersect with , 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

, 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 !
= Co-NP
{c}
{parent=NP (complexity)}
{wiki}
* https://math.stackexchange.com/questions/361422/why-isnt-np-conp "Why isn't NP = coNP?"
* https://stackoverflow.com/questions/17046440/whats-the-difference-between-np-and-co-np
* https://cs.stackexchange.com/questions/9795/is-the-open-question-np-co-np-the-same-as-p-np
* https://mathoverflow.net/questions/31821/problems-known-to-be-in-both-np-and-conp-but-not-known-to-be-in-p
= Optimization problem
{parent=Computational problem}
{wiki}
= Linear programming
{parent=Optimization problem}
{wiki}
= Logistics
{parent=Optimization problem}
{wiki}
= Last mile problem
{parent=Logistics}
The exact same problem appears over and over, e.g.:
* https://en.wikipedia.org/wiki/Last_mile_(transportation)[transportaion]: the last mile of the trip when everyone leaves the train and goes to their different respective offices is the most expensive
* https://en.wikipedia.org/wiki/Last_mile_(telecommunications)[telecommunications]: the last mile of wire linking local hubs to actual homes is the most expensive
* electrical grid: same as telecommunications
also identified knowledge version of this problem: .
= Optimization software
{parent=Optimization problem}
{tag=Software}
* https://en.wikipedia.org/wiki/List_of_optimization_software
* https://en.wikipedia.org/wiki/Comparison_of_optimization_software
= CPLEX
{c}
{parent=Optimization software}
= Limiting factor
{parent=Optimization problem}
{wiki}
= Critical path method
{parent=Limiting factor}
{wiki}
= Critical path
{parent=Critical path method}
= Dependency graph
{parent=Critical path method}
{wiki}
= Value function
{parent=Optimization problem}
{wiki}
The function being maximized in a .
= List of computational problems
{parent=Computational problem}
= 3SUM
{parent=List of computational problems}
{tag=Simple to state but hard to prove}
{wiki}
It is cool how even for such a "simple looking" problem, we were still unable to prove optimality as of 2020.
= Computer scientist
{parent=Computer science}
{wiki}
= Alan Turing
{c}
{parent=Computer scientist}
{wiki}
= Noam Chomsky
{c}
{parent=Computer scientist}
{tag=Cool person}
{wiki}
= Scott Aaronson
{c}
{parent=Computer scientist}
{wiki}
\Include[cryptography]{parent=computer-science}
= Hash function
{parent=Computer science}
{wiki}
= Hash
{synonym}
Applications:
* https://en.wikipedia.org/wiki/Hash_table[hash map] which is a O(1) amortized implementation of a map
* creating unbreakable chains of data, e.g. for https://stackoverflow.com/questions/22968856/what-is-the-file-format-of-a-git-commit-object-data-structure/37438460#37438460[Git commits] or .
* 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/
= Secure Hash Algorithms
{c}
{parent=Hash function}
{wiki}
= SHA
{c}
{title2}
{synonym}
= SHA-1
{c}
{parent=Secure Hash Algorithms}
{wiki}
= SHA-2
{c}
{parent=Secure Hash Algorithms}
{wiki}
= Merkle tree
{c}
{parent=Hash function}
= Hash tree
{synonym}
= Computer science bibliography
{parent=Computer science}
= Computer science YouTube channel
{parent=Computer science bibliography}
{tag=YouTube channel}
= Computerphile
{c}
{parent=Computer science YouTube channel}
{tag=Brady Haran production}
{wiki}
= Brady Haran
{c}
{parent=Computerphile}
{wiki}
= Brady Haran production
{c}
{parent=Brady Haran}
{tag=Science communicator}