CS6014 - Computability and Complexity

Meetings  

• Theme 1 : Computability Theory - 28 meetings

  • Meeting 01 : Mon, Jul 31, 08:00 am-08:50 am

  Administrative Announcements. Review of Turing machines. Definitions. Recursive and Recursively enumerable languages.

  References
  Exercises
  Reading

  Administrative Announcements. Review of Turing machines. Definitions. Recursive and Recursively enumerable languages.
  

  References:

  None

  • Meeting 02 : Tue, Aug 01, 12:00 pm-12:50 pm

  Introduction to Turing Machines. Informal definition. Formal definition. High level description of a Turing machine for an example language.

  References	[Koz1]
  Exercises
  Reading

  Introduction to Turing Machines. Informal definition. Formal definition. High level description of a Turing machine for an example language.
  

  References:

  [Koz1]

  • Meeting 03 : Thu, Aug 03, 11:00 am-11:50 am

  Full description of the TM for the example. Configurations, acceptance. Halting vs non halting. More examples.

  References	[Kozen Book 1]
  Exercises
  Reading

  Full description of the TM for the example. Configurations, acceptance. Halting vs non halting. More examples.
  

  References:

  [Kozen Book 1]

  • Meeting 04 : Fri, Aug 04, 10:00 am-10:50 am

  More examples. High level description of a TM for another non context-free language.

  References	[Koz1]
  Exercises
  Reading

  More examples. High level description of a TM for another non context-free language.
  

  References:

  [Koz1]

  • Meeting 05 : Mon, Aug 07, 08:00 am-08:50 am

  Lecture cancelled due to unavailability of the instructor.

  References
  Exercises
  Reading

  Lecture cancelled due to unavailability of the instructor.
  

  References:

  None

  • Meeting 06 : Tue, Aug 08, 12:00 pm-12:50 pm

  Extension of the Turing machine model: Multitape Turing machines. TMs with two way infinite tapes.

  References	[Koz1]
  Exercises
  Reading

  Extension of the Turing machine model: Multitape Turing machines. TMs with two way infinite tapes.
  

  References:

  [Koz1]

  • Meeting 07 : Thu, Aug 10, 11:00 am-11:50 am

  Lecture Cancelled.

  References
  Exercises
  Reading

  Lecture Cancelled.
  

  References:

  None

  • Meeting 08 : Fri, Aug 11, 10:00 am-10:50 am

  Non-deterministic Turing Machines. Simulating non-deterministic TMs by deterministic ones.

  References	Your class notes.
  Exercises
  Reading

  Non-deterministic Turing Machines. Simulating non-deterministic TMs by deterministic ones.
  

  References:

  Your class notes.

  • Meeting 09 : Mon, Aug 14, 08:00 am-08:50 am

  An encoding for TMs. Goedel numbering. Universal Turing machines. Recursive languages. Recursively enumerable languages.

  References	[Koz1]
  Exercises
  Reading

  An encoding for TMs. Goedel numbering. Universal Turing machines. Recursive languages. Recursively enumerable languages.
  

  References:

  [Koz1]

  • Meeting 10 : Wed, Aug 16, 04:50 pm-05:35 pm

  Recursive vs recursively enumerable languages. HP and MP are recursively enumerable. Cantor's diagonalization argument.

  References	[Koz1]
  Exercises
  Reading

  Recursive vs recursively enumerable languages. HP and MP are recursively enumerable. Cantor's diagonalization argument.
  

  References:

  [Koz1]

  • Meeting 11 : Thu, Aug 17, 11:00 am-11:50 am

  MP and HP are not recursive. Proof using Cantor's diagonalization.

  References	[Koz1]
  Exercises
  Reading

  MP and HP are not recursive. Proof using Cantor's diagonalization.
  

  References:

  [Koz1]

  • Meeting 12 : Fri, Aug 18, 10:00 am-10:50 am

  Classifying problems into recursive and non-recursive languages: Examples of recursive languages.

  References	[Koz1]
  Exercises
  Reading

  Classifying problems into recursive and non-recursive languages: Examples of recursive languages.
  

  References:

  [Koz1]

  • Meeting 13 : Mon, Aug 21, 08:00 am-08:50 am

  Examples of non-recursive languages.

  References	[Koz 1]
  Exercises
  Reading

  Examples of non-recursive languages.
  

  References:

  [Koz 1]

  • Meeting 14 : Tue, Aug 22, 12:00 pm-12:50 pm

  Closure properties of recursive languages: intersection, union. Non closure under complementation.

  References
  Exercises
  Reading

  Closure properties of recursive languages: intersection, union. Non closure under complementation.
  

  References:

  None

  • Meeting 15 : Thu, Aug 24, 11:00 am-11:50 am

  No lecture (Instructor out of town)

  References
  Exercises
  Reading

  No lecture (Instructor out of town)
  

  References:

  None

  • Meeting 16 : Fri, Aug 25, 10:00 am-10:50 am

  No lecture (holiday)

  References
  Exercises
  Reading

  No lecture (holiday)
  

  References:

  None

  • Meeting 17 : Mon, Aug 28, 08:00 am-08:50 am

  Notion of reductions. Recursively computable functions. Some example reductions.

  References
  Exercises
  Reading

  Notion of reductions. Recursively computable functions. Some example reductions.
  

  References:

  None

  • Meeting 18 : Tue, Aug 29, 12:00 pm-12:50 pm

  Non recursively enumerable languages. Rice's theorem: Part I.

  References
  Exercises
  Reading

  Non recursively enumerable languages. Rice's theorem: Part I.
  

  References:

  None

  • Meeting 19 : Thu, Aug 31, 11:00 am-11:50 am

  Rice's Theorem Part II. Relative computation.

  References	[Kozen1] and [Kozen2]
  Exercises
  Reading

  Rice's Theorem Part II. Relative computation.
  

  References:

  [Kozen1] and [Kozen2]

  • Meeting 20 : Fri, Sep 01, 10:00 am-10:50 am

  Oracle Turing Machine. Relativized computation. Arithmetic Hierarchy.

  References
  Exercises
  Reading

  Oracle Turing Machine. Relativized computation. Arithmetic Hierarchy.
  

  References:

  None

  • Meeting 21 : Mon, Sep 04, 08:00 am-08:50 am

  Quiz - 1

  References
  Exercises
  Reading

  Quiz - 1
  

  References:

  None

  • Meeting 22 : Tue, Sep 05, 12:00 pm-12:50 pm

  Relativized computation. Definition of the arithmetic hierarchy. Placing languages within the arithmetic hierarchy.

  References
  Exercises
  Reading

  Relativized computation. Definition of the arithmetic hierarchy. Placing languages within the arithmetic hierarchy.
  

  References:

  None

  • Meeting 23 : Thu, Sep 07, 11:00 am-11:50 am

  More languages within the arithmetic hierarchy. Notion of completeness. Complete problems for the first level of the AH

  References
  Exercises
  Reading

  More languages within the arithmetic hierarchy. Notion of completeness. Complete problems for the first level of the AH
  

  References:

  None

  • Meeting 24 : Fri, Sep 08, 10:00 am-10:50 am

  Complete problems for second level of the AH.

  References
  Exercises
  Reading

  Complete problems for second level of the AH.
  

  References:

  None

  • Meeting 25 : Mon, Sep 11, 08:00 am-08:50 am

  Peano arithmetic. Goedel's incompleteness theorem (statement).

  References
  Exercises
  Reading

  Peano arithmetic. Goedel's incompleteness theorem (statement).
  

  References:

  None

  • Meeting 26 : Tue, Sep 12, 12:00 pm-12:50 pm

  Proof of Goedel's incompleteness theorem (1)

  References
  Exercises
  Reading

  Proof of Goedel's incompleteness theorem (1)
  

  References:

  None

  • Meeting 27 : Thu, Sep 14, 11:00 am-11:50 am

  Proof of Goedel's incompleteness theorem (2)

  References
  Exercises
  Reading

  Proof of Goedel's incompleteness theorem (2)
  

  References:

  None

  • Meeting 28 : Fri, Sep 15, 10:00 am-10:50 am

  Solutions to Quiz - 1

  References
  Exercises
  Reading

  Solutions to Quiz - 1
  

  References:

  None

• Theme 2 : Complexity Theory: Resource Bounded Computability - 30 meetings

  • Meeting 29 : Mon, Sep 18, 08:00 am-08:50 am

  Resource bounded computations. Notion of resource. Time complexity.

  References	[Koz2] and Lecture notes by Markus Blaeser (mailed to the group).
  Exercises
  Reading

  Resource bounded computations. Notion of resource. Time complexity.
  

  References:

  [Koz2] and Lecture notes by Markus Blaeser (mailed to the group).

  • Meeting 30 : Tue, Sep 19, 12:00 pm-12:50 pm

  A quadratic time gap between single tape and multi-tape Turing machines.

  References	[Koz2] and Lecture notes by Markus Blaeser (mailed to the group).
  Exercises
  Reading

  A quadratic time gap between single tape and multi-tape Turing machines.
  

  References:

  [Koz2] and Lecture notes by Markus Blaeser (mailed to the group).

  • Meeting 31 : Thu, Sep 21, 11:00 am-11:50 am

  Time lower bound against single tape TMs.

  References	[Koz2] and Lecture notes by Markus Blaeser (mailed to the group).
  Exercises
  Reading

  Time lower bound against single tape TMs.
  

  References:

  [Koz2] and Lecture notes by Markus Blaeser (mailed to the group).

  • Meeting 32 : Fri, Sep 22, 10:00 am-10:50 am

  Time hierarchy Theorem.

  References	[Koz2] and Lecture notes by Markus Blaeser (mailed to the group).
  Exercises
  Reading

  Time hierarchy Theorem.
  

  References:

  [Koz2] and Lecture notes by Markus Blaeser (mailed to the group).

  • Meeting 33 : Mon, Sep 25, 08:00 am-08:50 am

  Notion of space. Space hierarchy. Blum's axioms.

  References	[Koz2] and Lecture notes by Markus Blaeser (mailed to the group). For Blum's axioms, please refer to the chapter "Abstract Complexity" in [Koz2]
  Exercises
  Reading

  Notion of space. Space hierarchy. Blum's axioms.
  

  References:

  [Koz2] and Lecture notes by Markus Blaeser (mailed to the group). For Blum's axioms, please refer to the chapter "Abstract Complexity" in [Koz2]

  • Meeting 34 : Tue, Sep 26, 12:00 pm-12:50 pm

  Axiomatic definition of resource: Blums axioms. Gap and Hierarchy as a consequence of the axioms. Robust Complexity Classes: DLOG, P, PSPACE, E and EXP.

  References	[Koz2]
  Exercises
  Reading	Read the original <a href="http://dl.acm.org/citation.cfm?id=321395"> article </a> by Blum.

  Axiomatic definition of resource: Blums axioms. Gap and Hierarchy as a consequence of the axioms. Robust Complexity Classes: DLOG, P, PSPACE, E and EXP.
  

  References:	[Koz2]
  Reading:	Read the original article by Blum.

  • Meeting 35 : Thu, Sep 28, 11:00 am-11:50 am

  Computational Problems: CLIQUE, VC, SAT, CNFSAT, FVAL, CNFEVAL and REACH

  References
  Exercises
  Reading

  Computational Problems: CLIQUE, VC, SAT, CNFSAT, FVAL, CNFEVAL and REACH
  

  References:

  None

  • Meeting 36 : Thu, Oct 05, 11:00 am-11:50 am

  Finding vs verifying solutions. Guess and Verifiy : notion of non-determinism.

  References
  Exercises
  Reading

  Finding vs verifying solutions. Guess and Verifiy : notion of non-determinism.
  

  References:

  None

  • Meeting 37 : Fri, Oct 06, 10:00 am-10:50 am

  Non deterministic time and space. Classes NP, NL, NEXP etc.

  References
  Exercises
  Reading

  Non deterministic time and space. Classes NP, NL, NEXP etc.
  

  References:

  None

  • Meeting 38 : Mon, Oct 09, 08:00 am-08:50 am

  Reductions. Polynomial time reduction. Clique polynomial time reduces to Independent set. Completeness. Cook-Levin Theorem.

  References
  Exercises
  Reading

  Reductions. Polynomial time reduction. Clique polynomial time reduces to Independent set. Completeness. Cook-Levin Theorem.
  

  References:

  None

  • Meeting 39 : Tue, Oct 10, 12:00 pm-12:50 pm

  Proof of Cook Levin Theorem.

  References
  Exercises
  Reading

  Proof of Cook Levin Theorem.
  

  References:

  None

  • Meeting 40 : Thu, Oct 12, 11:00 am-11:50 am

  Cook Levin Theorem (contd)

  References
  Exercises
  Reading

  Cook Levin Theorem (contd)
  

  References:

  None

  • Meeting 41 : Fri, Oct 13, 10:00 am-10:50 am

  CSAT to 3SAT reduction. VC is NP complete.

  References
  Exercises
  Reading

  CSAT to 3SAT reduction. VC is NP complete.
  

  References:

  None

  • Meeting 42 : Mon, Oct 16, 08:00 am-08:50 am

  Quiz - 2

  References
  Exercises
  Reading

  Quiz - 2
  

  References:

  None

  • Meeting 43 : Tue, Oct 17, 12:00 pm-12:50 pm

  VC is NP-complete (contd). Closure properties of NP. Is EXP vs NEXP related to P vs NP? Padding arguments.

  References
  Exercises
  Reading

  VC is NP-complete (contd). Closure properties of NP. Is EXP vs NEXP related to P vs NP? Padding arguments.
  

  References:

  None

  • Meeting 44 : Thu, Oct 19, 11:00 am-11:50 am

  Is there a problem in NP that is not NP complete and not in P?

  References
  Exercises
  Reading

  Is there a problem in NP that is not NP complete and not in P?
  

  References:

  None

  • Meeting 45 : Fri, Oct 20, 10:00 am-10:50 am

  Ladner's theorem

  References
  Exercises
  Reading

  Ladner's theorem
  

  References:

  None

  • Meeting 46 : Mon, Oct 23, 08:00 am-08:50 am

  Ladner's theorem (contd). Relativization. Relativized complexity classes.

  References
  Exercises
  Reading

  Ladner's theorem (contd). Relativization. Relativized complexity classes.
  

  References:

  None

  • Meeting 47 : Tue, Oct 24, 12:00 pm-12:50 pm

  NP^NP vs NP. Baker-Gill-Solovay: Existence of oracles for which P and NP coincide and oracle for which P and NP are separate.

  References	<a href="https://dspace.mit.edu/bitstream/handle/1721.1/106671/18-405j-fall-2001/contents/lecture-notes/01lec6.pdf">Notes </a> by Daniel Spielman. Also see Notes by Markus Blaeser (Shared in the google group).
  Exercises
  Reading

  NP^NP vs NP. Baker-Gill-Solovay: Existence of oracles for which P and NP coincide and oracle for which P and NP are separate.
  

  References:

  Notes by Daniel Spielman. Also see Notes by Markus Blaeser (Shared in the google group).

  • Meeting 48 : Thu, Oct 26, 11:00 am-11:50 am

  Baker Gill Solovay (contd). Sparse NP complete sets: Mahaney's theorem.

  References
  Exercises
  Reading

  Baker Gill Solovay (contd). Sparse NP complete sets: Mahaney's theorem.
  

  References:

  None

  • Meeting 49 : Fri, Oct 27, 10:00 am-10:50 am

  Mahaney's theorem (contd). Generalizations of NP. 1) Based alternating quantifiers. Definition of Polynomial Hierarchy. Examples. Circuit Minimization Problem, Formula Isomorphism Problem. 2) Characterization of PH in terms of relativizations

  References	For a list of problems complete for PH <a href="http://ovid.cs.depaul.edu/documents/phcom.pdf"> See here </a>.
  Exercises
  Reading

  Mahaney's theorem (contd). Generalizations of NP. 1) Based alternating quantifiers. Definition of Polynomial Hierarchy. Examples. Circuit Minimization Problem, Formula Isomorphism Problem. 2) Characterization of PH in terms of relativizations
  

  References:

  For a list of problems complete for PH See here .

  • Meeting 50 : Mon, Oct 30, 08:00 am-08:50 am

  Polynomial time hierarchy theorem: Characterization through quantifiers.

  References
  Exercises
  Reading

  Polynomial time hierarchy theorem: Characterization through quantifiers.
  

  References:

  None

  • Meeting 51 : Tue, Oct 31, 12:00 pm-12:50 pm

  Quantified Boolean Formulas. Completeness for PSPACE.

  References
  Exercises
  Reading

  Quantified Boolean Formulas. Completeness for PSPACE.
  

  References:

  None

  • Meeting 52 : Thu, Nov 02, 11:00 am-11:50 am

  NL vs L. Reach is in NL. NL is in P. Log-space reductions.

  References
  Exercises
  Reading

  NL vs L. Reach is in NL. NL is in P. Log-space reductions.
  

  References:

  None

  • Meeting 53 : Fri, Nov 03, 10:00 am-10:50 am

  Reach is complete for NL. Savitch's theorem. Closure properties of NL. Immermann-Szelepcsényi theorem.

  References
  Exercises
  Reading

  Reach is complete for NL. Savitch's theorem. Closure properties of NL. Immermann-Szelepcsényi theorem.
  

  References:

  None

  • Meeting 54 : Mon, Nov 06, 08:00 am-08:50 am

  Proof of Immermann-Szelepcsényi theorem.

  References
  Exercises
  Reading

  Proof of Immermann-Szelepcsényi theorem.
  

  References:

  None

  • Meeting 55 : Tue, Nov 07, 12:00 pm-12:50 pm

  TBA

  References
  Exercises
  Reading

  TBA
  

  References:

  None

  • Meeting 56 : Thu, Nov 09, 11:00 am-11:50 am

  TBA

  References
  Exercises
  Reading

  TBA
  

  References:

  None

  • Meeting 57 : Fri, Nov 10, 10:00 am-10:50 am

  To Be Announced

  References
  Exercises
  Reading

  To Be Announced
  

  References:

  None

  • Meeting 58 : Mon, Nov 13, 08:00 am-08:50 am

  To Be Announced

  References
  Exercises
  Reading

  To Be Announced
  

  References:

  None