Introduction to Cook Jokes

This is the last blog post.

We introduced several fields related to theoretical computer science in this blog. My objective was mostly to have some record of learning this material, and especially of dealing with the classification issues that arise.

Here are the best "Cook Jokes" that were made during the offering of Prof. Steve Cook's 2013-2014 complexity (463) and logic (438) courses.

Best Cook Jokes:

1. You just got Cookblocked!

• rationale: You are talking with a classmate when a pretty CS girl approaches you, however, it is only to stand in line to speak with Cook after lecture
• credit: Sean

2. If you had Rice, you could Cook almost anything

• rationale: If you have ever taken a Cook class, you know that it is forbidden to use Rice's theorem
• credit: Lex

3. You can Cook a Karp but you can't Karp a Cook

• rationale: Karp (and others) praised Cook's ground breaking work
• credit: Av

4. I think he Cooked the books...

• rationale: Says fellow student as Cook writes his own theorems on the blackboard and gives the reference in Sipser
• credit: Av

5. What's he Cooking up today?

• rationale: You are entering BA1220 as you hear these words, needless to say it never gets old
• credit: Sean

6. I compiled all the notes into a nice Cookbook

• rationale: Print out all the notes from Cook's lectures and staple them together
• credit: Lex

Introduction to Algorithms

Here, we briefly introduce the two interrelated fields of Algorithm Design and the Analysis of Algorithms.

Algorithm Design is a framework to study algorithmic design paradigms (what types of problems they can solve optimally, what data structures can be used, what algorithms are robust enough given nondeterministic settings...). The Analysis of Algorithms is the subfield of complexity theory that provides a framework for studying the running time and correctness of algorithms.

Here is an attempt to organise algorithms according to some important properties:

• recursive/iterative  | not using looping
• serial                       | parallel (= concurrent)
• "classical" parallel
• distributed
• exact                        | approximate
• deterministic            | nondeterminisitic*
• not using randomness | probabilistic (= randomized)
• Monte Carlo (ND solution)
• Las Vegas (ND runtime)
• not using heuristics     | heuristic based*

Here is a classification by design paradigm:

• Brute Force - Try every candidate solution in the search space until a solution is found.
• Divide and Conquer - Break the problem down to its most trivial subproblems and recombine solutions bottom-up.
• Dynamic Programming - Remember solutions to some subproblems in a table so there is no need recompute them.
• Greedy Method - Order candidate solutions in an informed way to avoid exploring the entire search space.
• Linear Programming - Optimization of a function given linear constraints.
• Other Search/Enumeration/Optimization design paradigms
• Backtracking - Depth first search on search space (tree), only exploring branches where possible solutions can lie.
• Branch and Bound - Special backtracking where bounding is a bit more sophisticated.
• Hill Climbing - Make a move in the search space and see if it improves the objective function and keep on going in that direction.
• Local Search - Move to the neighbour in the search space that improves the objective function the most.
• Tabu Search - Local Search that avoids (by prior or learning) tabu areas in the search space.
• Simulated Annealing - Probabilistic exploration of the search space based on decreasing the entropy of the decisions slowly with time.
• Genetic Algorithm - Algorithm that simulates evolution, ensuring that the genes of the genotype that is the most fitted to its environment (according to some objective function) are more likely to be carried over to the next generation.

Notes (*):

Nondeterminism: when behaviour cannot be predicted deterministically from state and input. There is some discrepancy in the terminology here again:

• Generally, nondeterminism is equivalent to randomness and stochasticity. It can arise from the algorithm itself (i.e. a probabilistic alg) or from externalities (i.e. because of the implementation setting - e.g. a parallel alg running on a system with a race condition).
• In Complexity Theory, nondeterminism has a very specific sense: a nondeterministic machine can branch its thread of execution at any point in the control flow; so a ND alg here is one that can run on a ND model of computation. Notice that the result is deterministic!

Heuristic: If you have taken a psychology course before, you might have learned that the difference between an algorithm and a heuristic regards optimality of the solution, so how about approximation algs or heuristic algs? To reconcile terminology, we consider "heuristic algorithms" (or "heuristic-based algs") as synonym of "algorithms making some use of heuristics" but we exclude heuristics as algorithms:

• A heuristic-based algorithm integrates in its logic strategie(s) that improve some aspect of the behaviour of the alg without providing rigorous info about the tradeoffs they induce.
• A heuristic can be viewed as a pure heuristic-based alg (the heuristical aspect applies to the purpose of the alg itself, hence the induced tradeoff here always affects the optimality of the solution). In this sense, heuristics are approximation algs for which we don't have info on the approximation ratio.

As a field of study, the Design and Analysis of Algorithms - or simply "Algorithms" - lacks an overarching formalism (Bellman, Borodin...), even the definition of algorithm itself is not generally agreed upon (if you have time: http://en.wikipedia.org/wiki/Algorithm_characterizations).

Computability and Complexity

Here, are my notes on Computability Theory and Computational Complexity Theory.

Recommended Reading:

Read all of Sipser for an excellent intro, then move on to my favourite TCS book: Savage's Models of Computation (http://cs.brown.edu/~jes/book/).

Introduction to Mathematical Logic

Here, we introduce the field of Mathematical Logic.

This is by far my favourite topic ^_^, the heart of TCS:

TCS was born out of the endeavours of metamathematicians during the Grundlagenkrise at the beginning of the 20th century, some good reads on the topic are:
Contributions of the Logicians by Burris (https://www.math.uwaterloo.ca/~snburris/htdocs/history.html) and Logicomix by Doxiadis and Papadimitriou (warning: you might get frustrated by Papa constantly barging in, the lack of math and/or the "cliffhanger"!)

From the metaprocesses of Life (evolutionary processes), the human brain has been structured with the capacity for rationality/reason (stemming from fitedness with the seemingly inherent order of the Universe). Logic is the study of using this capacity (notice that it is itself required to study itself!); while Mathematics is using this capacity to study the abstract notions of quantity (arithmetic), structure (algebra), form (topology) and change (analysis).

Without going into the philosophical underpinnings of reasoning (Hume's problem of induction, Grue and Bleen, Occam's razor, etc.), what is important to know about the range of Logic is the following:

Logic has 2 definitions:
(functional) the use of reasoning
(structural) the field of study

The field of study is commonly divided in 3 parts:

• deductive reasoning - drawing conclusions from premises (cf. entailment, modus ponens, syllogisms, material conditional)
• inductive reasoning - given complete (unbiased sample), draw conclusions on the entire population
• abductive reasoning - given incomplete observations, infer to the best explanation

However, it is also possible to partition it according to the framework in which it is studied:

• informal logic - no definite setting
• formal logic - formal setting

Formal Logic (also called Mathematical Logic or Symbolic Logic) is thus the approach to Logic using the setting of formal systems, which are "broadly defined as any well-defined system[s] of abstract thought based on the model of mathematics" -- Wikipedia.

But Mathematical Logic also has another definition, that is, as a branch of Mathematics born out of the field of study denoted as "foundations of mathematics" as mentioned in the introduction. Thus wedged between Logic and Mathematics, Mathematical Logic is a cornerstone of Metamathematics (which will definitely be the topic of a future post ^_*).

Mathematical Logic has 2 definitions:
(logic) formal logic as defined previously
(mathematics) the subfield of Mathematics encompassing the "four pillars of the foundations of mathematics": set theory (sets)[~quantity], proof theory (syntax)[~structure], model theory (semantics)[~form], recursion theory (computation)[~change].

Under the latter definition, notice that Computability Theory (recursion theory) is as much a (seminal) subfield of TCS as it is a subfield of Math Logic.

Under the former definition, Formal Logic is commonly partitioned into:

• Classical Logics
• boolean logic - algebra of truth (BL)
• propositional (sentential) logic - 0th order logic, a.k.a. propositional calculus (PL)
• predicate logic - higher-order logics, e.g. first order logic (FOL), second order logic (SOL), infinitary logic, many-sorted logics
• Non-Classical Logics
• modal logic - extends classical logic with non-truth-functional ("modal") operators
• provability logic - changes necessity operator to provability operator
• interpretability logic - extend provability logic to describe interpretability
• many-valued logics - a propositional calculus in which there are more than two truth values
• fuzzy logic - allows as a truth value any real number between 0 and 1
• intuitionistic (constructive) logic - replaces truth by "constructive provability"; rejects the law of the excluded middle and double negative elimination
• paraconsistent logic - rejects the law of noncontradiction
• relevance logic - replaces material conditional (implication) by requiring that antecedent and consequent be related by some "relevance"
• non-monotonic logic - rejects monotonicity of entailment
• default logic - formalizing reasoning with default assumptions
• autoepistemic logic - formalizing reasoning of knowledge about knowledge

Just as the interconnectivity of Mathematics doesn't allow all its subfields to be represented in a planar graph, there is no clean scheme for classifying formal logics, and the one above is division is a mesh of generalising or relaxing some properties, such as properties common to the class of classical logics:

• law of noncontradiction - two contradictory statements cannot both be true at the same time
• law of the excluded middle - statements are either true or false
• monotonicity of entailment - statements derived from a premise can be derived from that premise and any other premise (if they are contradictory, then we get vacuous truth)
• idempotency of entailment - statements that can be derived from a single instance of a premise, can also be derived from multiple instances of the same premise and vice-versa
• commutativity of conjunction - conjuncts can be switched without affecting truth value
• DeMorgan duality - dichotomies of unary and binary logical operators

The first two laws come from Aristotle's laws of thought:
"The law of noncontradiction, along with its complement, the law of excluded middle (the third of the three classic laws of thought), are correlates of the law of identity (the first of the three laws). Because the law of identity partitions its logical Universe into exactly two parts, it creates a dichotomy wherein the two parts are "mutually exclusive" and "jointly exhaustive". The law of noncontradiction is merely an expression of the mutually exclusive aspect of that dichotomy, and the law of excluded middle, an expression of its jointly exhaustive aspect." --Wikipedia

Notice that this dichotomy of truth core to classical logics is reflected in (equivalent) laws:

• the principle of explosion (ex falso quod libet) - anything can be proven from a contradiction
• e.g. A is true and ~A is true, thus A or B is true (or intro), thus A or B and ~A is true (and intro), thus B is true (skipped steps but using principle of noncontradiction)
• the principle of vacuous truth - if the antecedent is false in a conditional statement, the statement is true

Finally, let us briefly touch upon another dichotomy inherent to the structure of formal logic, syntax vs semantics, by properly distinguishing material from logical consequence in the context of classical logic:

logical implication (semantic) as defined in classical logic:

\Phi \models (double turnstile in latex) A iff any truth assignment satisfying \Phi also satisfies A

note: the definition happens in the metalanguage that is used to define the object language, thus symbols like "iff" and notions of truth assignments and satisfiability are about the language that is being defined. We will see later that when logics can express statements about their own statements, interesting issues arise.

material conditional (syntactic) as defined in classical logic:

A \supset B iff ~A \vee B                (A implies B iff notA or B)

note: to quickly remember this result think about sets: A implies B means that the elements in set A (i.e. that have property A) are also elements of B (i.e. have property B), thus B contains A. That only means that there can be no elements in A that are not in B (not(A and notB)). Using DeMorgan this is equivalent to the statement above. In this sense B is a broader (also termed stronger, see below) property.

note about the note: there is a confusion I want to resolve here: stronger vs weaker statements. Generally, if assumptions are stronger than others it means that they imply the weaker ones; however the confusion arises when talking about properties: a property that holds on weaker assumptions is stronger (more general) than one that holds on stronger assumptions.

Thus, we conclude our preliminary overview of Math Logic by pointing out that such interconnected notions are best approached from multiple directions, a fact that is true for any concept the brain can handle (cf distributed representations), but that gets amplified as the concepts become more abstract. What does this fact say about the human capacity for abstraction? What does it say about the frame problem?

Further reading:

http://www.iep.utm.edu/logcon/

http://plato.stanford.edu/entries/logic-classical/

http://en.wikipedia.org/wiki/Logic_in_computer_science

http://en.wikipedia.org/wiki/List_of_logic_symbols