Ciro Santilli
OurBigBook.com
$£
Sponsor
中国
独裁统治 China Dictatorship 新疆改造中心、六四事件、法轮功、郝海东、709大抓捕、2015巴拿马文件 邓家贵、低端人口、西藏骚乱
Computational problem
Home
Technology
Area of technology
Information technology
Computer
Computer science
OurBigBook.com
words: 2k
articles: 88
The list:
complexityzoo.uwaterloo.ca/Complexity_Zoo
Table of contents
2k
88
Decision problem
Computational problem
2k
28
Halting problem
Decision problem
1k
27
Turing machine decider
Halting problem
403
4
Turing machine regex tape notation
Turing machine decider
166
Cycler Turing machine
Turing machine decider
98
Translated cycler Turing machine
Turing machine decider
37
Closed Tape Language decider
Turing machine decider
2
Busy beaver
Halting problem
1k
21
Step busy beaver
Busy beaver
47
Busy beaver function
(
B
B
(
n
)
)
Busy beaver
427
13
Specific values of the Busy beaver function
Busy beaver function
399
12
Turing machine acceleration
Specific values of the Busy beaver function
61
Busy Beaver Challenge
Specific values of the Busy beaver function
69
BB(5)
(Busy beaver function of 5)
Specific values of the Busy beaver function
165
4
Marxen-Buntrock machine
(1989, 4098 1's, ~47M steps)
BB(5)
31
Skelet’s machines
(2003)
BB(5)
51
2
Skelet machine #1
(proved 2023, cyclel start: 50-200M, period: ~8B)
Skelet’s machines
47
1
Skelet machine #1 is infinite
Skelet machine #1
45
BB(6)
(Busy beaver function of 6)
Specific values of the Busy beaver function
39
4
BB(6) is hard
BB(6)
39
3
Antihydra
(28 Jun 2024)
BB(6) is hard
3
2
Antihydra GMP implementation
Antihydra
gmp/antihydra.c
Antihydra
3
Busy beaver scale
Busy beaver
448
5
Turing machine compiler
Busy beaver scale
Automated theorem proving by halting problem reduction
Busy beaver scale
152
3
Conjecture reduction to a halting problem
Automated theorem proving by halting problem reduction
71
2
Turing machine that halts if and only if the Goldbach conjecture is false
(27-state)
Conjecture reduction to a halting problem
Turing machine that halts if and only if Collatz conjecture is false
Conjecture reduction to a halting problem
39
Function problem
Computational problem
183
6
Integer multiplication
Function problem
Integer factorization
Function problem
97
2
Integer factorization algorithm
Integer factorization
NP-hard cryptosystems
Integer factorization
47
Discrete logarithm
Function problem
68
1
Discrete logarithm of the cyclic group
Discrete logarithm
44
Algorithm
Computational problem
37
15
Algorithm cheatsheet
Algorithm
10
Data structure
Algorithm
22
6
Associative array
(map, dictionary)
Data structure
22
3
Binary search tree
(BST)
Associative array
14
1
B-tree
Binary search tree
14
Hash table
(Hash map)
Associative array
Dynamic array
Data structure
Linked list
Data structure
Recursion
(computer science)
Algorithm
2
Iteration
Recursion
1
Iterative algorithm
Iteration
Sorting algorithm
Algorithm
2
String-sorting algorithm
Sorting algorithm
1
Natural sort order
String-sorting algorithm
String-search algorithm
Algorithm
Complexity class
Computational problem
560
22
Time complexity
Complexity class
1
Quasilinear time
(
O
(
n
lo
g
k
(
n
)
)
)
Time complexity
Big O notation family
Complexity class
149
2
Big O notation
(
O
(
n
)
)
Big O notation family
69
Little-o notation
(
o
(
n
)
)
Big O notation family
53
Primitive recursive function
Complexity class
215
2
Non-primitive total recursive function
Primitive recursive function
33
1
Ackermann function
Non-primitive total recursive function
33
Galactic algorithm
Complexity class
ELEMENTARY
(complexity,
2
n
,
2
2
n
, ...)
Complexity class
196
12
EXPTIME
ELEMENTARY
196
11
NP
(complexity)
EXPTIME
196
10
P
(complexity, Polynomial time)
NP
1
Polynomial time algorithm
P
NP-complete
NP
39
3
Cook-Levin theorem
NP-complete
P versus NP problem
(P vs NP)
NP-complete
32
1
Ladner's Theorem
P versus NP problem
NP-hard
NP
15
NP-intermediate
NP
130
1
BQP
NP-intermediate
95
Co-NP
NP
5
Optimization problem
Computational problem
70
10
Linear programming
Optimization problem
Logistics
Optimization problem
63
1
Last mile problem
Logistics
63
Optimization software
Optimization problem
1
CPLEX
Optimization software
Limiting factor
Optimization problem
3
Critical path method
Limiting factor
2
Critical path
Critical path method
Dependency graph
Critical path method
Value function
Optimization problem
7
List of computational problems
Computational problem
21
1
3SUM
List of computational problems
21
Tagged
(2)
Average length of a Snakes and Ladders game
Matrix multiplication algorithm
Ancestors
(6)
Computer science
Computer
Information technology
Area of technology
Technology
Home
Incoming links
(4)
Algorithm
Decision problem
Quantum approximate optimization algorithm
Variational quantum eigensolver
Ciro Santilli
OurBigBook.com