.Open 20 . Schedule .Table Date .Item Meet .Item $Study(2 pts) .Item Bring(5 pts) .Item $Topic(5 pts) .Item Notes .Row Mon Apr 3 .Item 1 .Item - .Item - .Item Survival .Row Wed Jun 7 .Item 19 .Item Chapter 11 sections 11.5, 11.6 .Item Ex .Item Primality .Row Mon Jun 12 .Item 20 .Item Chapters 8, 9, 10, 11 .Item $Ex .Item Review .Row Fri Jun 16 .Item Final .Item Chapters 1, 2, 8, 9, 10, 11 .Item - .Item Comprehensive (200 pts) .Row Tue Jun 20 .Item - .Item - .Item - .Item Grades Due in .Close.Table . Ex Take the hand out from class 19 and see if you can match up what it says with what we have been studying in this course. Extract one point of similarity or an application of the theory in this class to the paper. Write it up as a single paragraph and bring to class. . Challenge I just met a class of puzzles for children. You are given a number of jugs of different sizes and want to use them to measure out a particular ammount. One instance: You have jugs that contain 4, 5, and 12 cups of water. Show how to get precisely 3 cups of water by filling and pouring water between the three jugs. These are entertaining and sometimes challenging. (1) formulate them as a problem that could be input into a TM. (2) Are the problems decidable, recursive, NP, P, NP-complete or what? Description of problems in Psychology course .See http://www.cog.brown.edu/courses/42/lec13.htm .Open Surprise I've just been told about the following paper which uses the content of this course to understand "Agents": Wooldridge M., Dunne P. The complexity of agent design problems: Determinism and history dependence Annals of Mathematics and Artificial Intelligence 45(3-4): 343-371, Abstract: .Box The .Key agent design problem is as follows: given a specification of an environment, together with a specification of a task, is it possible to construct an agent that can be guaranteed to successfully accomplish the task in the environment? In this article, we study the computational complexity of the agent design problem for tasks that are of the form "achieve this state of affairs" or "maintain this state of affairs." We consider three general formulations of these problems (in both .Key non-deterministic and deterministic environments ) that differ in the nature of what is viewed as an "acceptable" solution: in the least restrictive formulation, no limit is placed on the number of actions an agent is allowed to perform in attempting to meet the requirements of its specified task. We show that the .Key resulting decision problems are intractable , in the sense that these are non-recursive (but .Key recursively enumerable ) for achievement tasks, and non-recursively enumerable for maintenance tasks. In the second formulation, the decision problem addresses the existence of agents that have satisfied their specified task within some given number of actions. Even in this more restrictive setting the resulting decision problems are either .Key pspace-complete or np-complete. Our final formulation requires the environment to be history independent and bounded. In these cases polynomial time algorithms exist: for deterministic environments the decision problems are nl-complete; in non-deterministic environments, p-complete. .Close.Box . When it comes to the example of MDG at the bottom, partitioning of G into n clusters. Could you please explain it? We'll discuss it in class. .Close .Open Review . Table of Problem/Language classes .Table Type of Problem Machine Accepts Rejects RunTime on n symbols .Row Regular FSA L L_bar n .Row CFG NDPDA L L_bar n .Row P DTM L L_bar O(n^c) .Row NP NTM L L_bar O(n^c) .Row NP-complete NTM L L_bar O(n^c) but worse than rest .Row PS=NPS TM L L_bar O(c^n) but space is O(n^s) .Row RP Random TM L probably L_bar always O(n^c) .Row ZPP Random TM L L_bar O(n^c) on average .Row Recursive TM L L_bar Never infinite .Row Decidable TM L L_bar Never infinite .Row Undecidable ? .Row RE TM L ? Perhaps infinite .Row not RE None .Close.Table . Cooke's paper .See http://www.claymath.org/millennium/P_vs_NP/ .See http://www.claymath.org/millennium/P_vs_NP/Official_Problem_Description.pdf . The Complexity Zoo .See http://qwiki.caltech.edu/wiki/Complexity_Zoo .Open Questions . Why are there are so many complexity classes. Some seem very similar to others. Could you please explain again why there are so many complexity classes? . Which of the problem classes are the most important to remember? I think the probabalilstic ones RP and ZPP are probably least valuable and R, RE, P, NP, NP-complete the most critical. . What might we expect for final questions on chapters 1 and 2? Theory based, calculation based, both? Not much.... Chapter 1 is use thruout the rest of the course and final... Chapter 2: you need to know the definitions of the various kinds of automata and their languages -- and how they differ from TM's and their languages. Also you may have to use the definitions in an informal proof. But the real focus in this class is on TMs. . In Q.1 of the Final Exam Review Sheet, TM and Languages, what is "Languages" referring to ? In complexity theory the main purpose of machines is to recognise languages. So for each type of machine a language is defined -- typically by the machine entering a particular set of states. Examples: .Hole . Could you give a couple simple examples of formally written 'Induction' and 'Reduction' proofs? First a distinction: similar names but different in all other respects. .Key Induction is used to get a handle on infinite bu countable situations: numbers, strings, trees, .... Things that grow on piece at a time. The plan is to establish the truth of a few simple cases and then demonstrate that as we grow the complex objects the property remains true. Example of Induction All my Lego blocks are Green. So all I can construct are green objects. .Key Reduction is only used in the theory of computation. You already know that some problem P1 is difficult/impossible/hard and want to show that a new problem P2 is at least as bad. The plan od attack is to show that if we solve P2 then it is easy to solve P1.... but P1 is hard/impossible so must P2 be. Example of reduction -- this comes from the paper I'm reviewing above: Reducing the existence problem for an agent to the construction problem for an agent. The problem of constructing an ajent must be harder then checking for an agent existence, because construction prove existence. . Can you go over an example of a NP-Complete problem? TSP? Vertex Cover? Minesweeper! .Open Can you go over the reduction of NP-Complete problems? Minesweeper is NP Any instance of SAT can be expressed as a Minesweeper game! .Open Proof Encode boolean variables as a pair of unknpown squares surrounded by 1s. Encode 'wires' connecting different occurences of variables. Encode a NOT gate... Encode an AND gate Therefore can encode any boolean expression. Choosing the correct squares in each pair expresses SAT. .Close .Close . L[d] Could you please go over the language L[d] again? From my understanding it is the set of strings that won't make valid TMs. However, there are several proofs that use a TM for L[d]? L[d] is the "Diagonalization Language" defined in section 9.1.3 (pp370-372) which plays aa critical part in section 9.1.4 and the proof of 9.2. .See ./10.html#9.1.3 The Diagonalization Language 370 and .See ./10.html#L_d It is not the set of strings that don't make TMs.... but something more subtle. It is the language made up strings that describe TM's with a special (weird) property: they refuse to accept their own description as an input string. Perhaps L_d should be called "the Knockturn Alley" language? Here is an analogy: suppose I founded a new library that contains nothing but library catalogs -- it might will include on its shelves it's own catalog. So of course we would have to include the library's catalog in its own catalog. In fact we could imagine collecting a list of libraries that have put their own catalog on their shelves. And perhaps more interesting put on an exhibit of catalogs of libraries that don't have their own catalog listed in their catalog. The problem starts if we decide we want a library of catalogs that don't list their own catalogs.... do we list this libraries catalog or not? .Close Questions .Close Review .Close 20 . Next The comprehensive final on `FRIDAY` June 16. Let me know if this is impossible -- SOON. . Notes (Study): Read & think about the Course. What questions do you need answered? Submit one question by selecting the submit button at the top of the web page. To earn complete credit you need to do this at least 90 minutes before the start of class. (Topic): To earn all the possible points you must: turn up on time, not leave early, present work when called upon, and take part in discussions.