- The Chomsky hierarchy of formal languages.
- Regular languages/(non-deterministic and deterministic) finite state automata/regular expressions/left-linear and right-linear context-free grammars.
- Pumping lemma for proving non-regularity of languages
- Deterministic push-down automata (and whatever class of languages these are equivalent to)
- Context-free grammars/push-down automata
- Ambiguity
- Griebach Normal Form
- Chomsky Normal Form and membership test Cocke-Younger-Kasami (CYK) algorithm.
- Pumping lemma for proving language to be not context-free.
- An offhand mention of context-sensitive language
- Recursively enumerable languages/Turing Machines.
- Computability (unfortunately we were not able to solve does P=NP and win that new car).
- P time
- NP time
- NP-hard vs. NP-complete vs. NP
- Decidability vs. intractability

What I was disappointed about was the treatment of computability and exactly what the heck it means to be P or NP. I came away feeling only a little less confused about the problem than I was when I started the class.

As always, I went to google. I found a great explanation on stackoverflow (scroll to grom's answer) that was a good balance between layman's terms and formal terms I learned in class.

From my understanding now:

**P problems**are a class of problems where there is a known algorithm that can provide an answer/solution to the problem in polynomial time. Polynomial time can be O(1), O(n), or O(n^100000000). It doesn't matter.**NP problems**are a class of problems where we can guarantee there exists a solution, but we can't compute it in polynomial time; it can only be computed in non-deterministic polynomial time. What that means is that there exists a finite, polynomial amount of steps to find the solution but we can't describe a polynomial algorithm to reach it. We have to resort to an exhaustive, "brute-force" search for the solution. This is a problem because some NP problems are intractable which means even though it's possible to find an answer it may take so long it's not even worth it.**NP-complete problems**are problems that are NP but have the special property that all other NP problems can be reduced to them in polynomial time. This "simply" means any NP problem can be transformed into the NP-complete problem using a polynomial time algorithm.**NP-hard problems**are problems that are at least as difficult to solve as the hardest NP problem(s). Note, this class of problems includes problems that are harder than any NP problem (which means they may not even be solvable in non-deterministic polynomial time).

## No comments:

## Post a Comment