Complexity Flashcards
1
Q
What is algorithmic complexity
A
The shortest computer program required to generate a sequence, such as DNA.
ACGTACGTACGTACGT- Shorter
TCGAGCTAG- longer
1st one can use the fact that it is repeated to generate a shorter algorithm.
2
Q
What is logical depth
A
despite algorithmic equality, the amount of steps that is takes to complete.
All combinations of 3
all combinations of 4.
3
Q
What is crypticity
A
How DIFFICULT it is to generate the shortest computer program
4
Q
Dimensions
A
- Fractals are generated from simple recursive algorithms
- Self similar at all scales,
- infinite surface area
- orgin of power laws
some things dont fit into an integer dimension- fractals.
Fractals can satisfy power laws, this is seen in the real world, the times between earthquakes, metabolic scaling tyheory, mandelbrots.
5
Q
Ways to define complexity
A
Algorithmic, logical depth, crypticity, dimensions.
