A friend was cleaning our their bookshelf and gave me their spare copy of this book. If you are interested in turning machines, intractability, P = NP or P != NP this is probably the textbook for you. Not having a formal compute science background I had a hard time following some sections.
Chapter Notes & Quotes
- Regular Languages
- Pretend to be an automaton, you receive and input string and must determine whether it is a member of the language the automaton is supposed to recognize. You see the symbols in the string one by one and after each, you must decide whether the string so far is in the language.
- Deterministic finite automaton (DFA) - When the machine is in a given state and given the next symbol we know with 100% certainty what the next state will be.
- Nondeterministic finite automaton (NFA) - When the machine is in a given state and given the next symbol several choices may exist for the next state.
- After an NFA reads a symbol it splits into multiple copies of itself and follows all possible paths in parallel. Each copy proceeds as before, and if there are subsequent choices, it splits again. If the next symbol doesn’t appear on any of the arrows exiting this path’s state, the copy dies. If any copy are in the accept state then the input string is considered accepted.
- NFAs are like a parallel computation where several processes are running concurrently.
- Every deterministic finite automaton is automatically a nondeterministic finite automaton.
- Every NFA can be converted into an equivalent DFA.
- Context-Free Languages
- Pushdown automata - Like a nondeterministic finite automata but have a stack.
- The Church-Turing Thesis
- Decidability
- Certain problems are algorithmically solvable and others are not.
- Knowing a problem is unsolvable is useful because you know it must be simplified or altered before you can find a solution.
- Even some ordinary problems that people want to solve turn out to be computationally unsolvable.
- Reducibility
- Primary method for proving that a problem is computationally unsolvable.
- Reduction - Converting one problem to another problem so the solution to the first problem can be used to solve the second. Ex: Problem of measuring rectangle’s area reduced to measuring its width and height.
- Advanced Topics in Computability Theory
- Any incompressible string has roughly an equal number of 0s and 1s.
- Time Complexity
- Exponential time algorithms typically arise when we search through a space of solutions (brute-force search).
- Polynomially Equivalent - The algorithm can simulate another with only a polynomial increase in running time.
- Polynomially Verifiablity - Verifying the answer can be done in polynomial time.
- If a polynomial time algorithm exists for an NP-complete problem then all problems in NP would be polynomial time solvable.
- P = membership can be decided quickly.
- NP = membership can be verified quickly.
- Space Complexity
- Intractability
- Advanced topics in complexity theory
- Optimization problems seek to find the best solution among a set of possible solutions.
- Fermat test provides a probabilistic test for primality. We call a number pseudoprime if it passes all Fermat tests.
- Gain evidence of a code’s security by showing that the complexity of breaking the code is linked to a the complexity of some other problem for which there is compelling evidence of intractability.
- Private-Key Cryptosystem - The same key is used for both encryption and decryption.
- Public-Key Cryptosystem - The private decryption key is different than the public encryption key.