Instructor: Lane A. Hemaspaandra.
Grad TA: Ethan Johnson.
Undergraduate TAs: Shir Maimon and Colin Pronovost.
Course Information Document/Syllabus: Version 1.3.0.
Course Announcements/Library Reserves/Etc.: Reserves via Blackboard, Announcements mostly via Blackboard but also there will be Notes on this page in the Day-to-Day list.
Prerequisite: CSC 280.
Navigation Information:
Sometimes, I'll build a chunk of the web page in parallel and then export it to the web at one moment.
Note that even if you do the above things, sometimes browsers hold things without rechecking them. This most typically happens on things such as postscript documents called by links from web pages (even when it knows to recheck the web page each time, a browser may be too lazy to do that for files in its cache). If you have problems with that, simply emptying your cache should get you the fresh version of the object. Note that in Netscape/Mozilla/Firefox, if you find that it seems not to be grabbing the most current version of a web page (and on some browsers, using the forward/back buttons evades even the most emphatic preference settings), it often helps to simply use Shift-[ReloadButton] to tell it, "Go check again."
Disclaimer: Hey, I'm a theory professor, so I'm probably the worst person imaginable to take advice from on taming your browser.
P.S. A bit of additional browser advice, from a Firefox fan:
[Here is] how to tune cache settings for Firefox. The following steps are used do it: 1) Type "about:config" (without quotes) in URL bar, press ENTER, 2) Find key "browser.cache.check_doc_frequency", 3) Change value to "1", which means "Check every time I view the page". That should do it. The default is "3 (default): Check when the page is out of date (automatically determined)", but that does not always work.
Oh... a big exception of course regards quizzes and any posted answers (if any). Those always have slots right on their day, which often start empty (such as "TBA" or "To appear"), and as soon as those exist, they appear there but you know already that that is where they will appear (but if we CHANGE an answer set after we put up a first attempt, for example, we will typically give a clear heads-up via an explicit note or BB announcement, alerting you to that, as THAT you might otherwise miss). Another slight exception is I'll sometimes take the very last note, if IT is what has to be revised, and change its time to "revised at"... but I'll typically only do that if the change is such a big one that it will jump off the page at you, and I won't do it often at all (quite possibly, never, in fact).
In particular, though we will quickly (since much of that you should know from CSC 280) read or cover quite a bit about undecidability, we can't possibly build the MTH150 course (the undergraduate discrete math course) into this course. So, do make sure that you know (as in, by this coming Monday's class at latest) the equivalent of MTH150. As to what that means, you can easily see that (and, implicitly, what to read in Rosen) from the MTH150 web site's course outline.
By the way, you are responsible for all the readings, even if you have bad luck and the reserve copies are heavily checked out. It is true that the reserve copies can get very busy during the few days before a class (that might have a surprise quiz---and they all might) or before a homework set is due, so if you want to use those, you'll want to start very early to be safe.
We will have just one quiz on Monday---on proving things undecidable. On it, you MAY give either a Sipser-esque contradiction, or a reduction-based proof, all of course within whatever constraints the quiz puts on you. (And you can bring one sheet of HANDWRITTEN BY YOU notes if you wish---see the BB Announcements posting from an earlier day for more details, and after Monday the syllabus will spell all that out in extreme detail.) The diagnostic quiz, whose answers are posted under 8/30, gives in the answer set a good sample of a solution (except the quiz question was exceptionally simple, on purpose).
The office hours and review session's times, and all locations, were all posted in the BB announcements area today. Use them please!!! They also will be in the course information document as soon as it goes up, and it will go up before Monday's class.
BUT... teaching those first few dozen slides is sooooo urgent to get to, that on Monday we'll do that (and have a quiz). And then one Wednesday, we will have one in-class quiz and will start one take-home quiz. (Yes, so we actually are back down to just having 3 quizzes next week. So you all were right in saying 3; I was planning 4, but the fact that we covered all sorts of other stuff today shifted the plans.) And as to material, unless I think you can just read the syllabus/course information document on your own (in which case we'll spend Wed. on material, except for explicitly covering in detail academic honesty as that is very important to cover, and also the course grading basis), we'll (aside from the in-class quiz) spend Wednesday covering the course information document.
One or both of these will be asked on Monday's quiz (it is ok to bring in on your notes sheet answers, but it must be in your own words, otherwise you will have academic honesty problems on your Monday quiz; that is, put onto your note sheet only things you have generated from your knowledge and mind and understanding, even if you first gained an understanding via the review session). (Also, the quiz on Monday might ask other things, e.g., it might re-test you on the preface of the Hem-Ogi book, or other parts of the reading, or it might test your understanding of the syllabus, which document I mention has many aspects, ranging from rules to grading basis to number of drops to academic honesty---read it and know them. In fact, it is possible that more than one of these things will be on the Monday quiz.)
So, the two problems are as follows. For both, let us take it that HP is encoded over the alphabet {0,1} and that all the sets these problems are speaking of must be over the alphabet {0,1}. Also, we say that A and B have a recursive separator if there is a recursive set C such that A \subseteq C and C \subseteq \overline{B} (that is, all elements of A are members of C, yet no elements of B are members of C). (I suggest your draw yourself a picture, to help understand what this looks like. Each a set C is an easy set that is basically fencing A away from B, very informally put.)
1. Prove that every two disjoint (i.e., their intersection is empty) coRE sets have a recursive separator.
2. Prove that there exist two disjoint RE sets that have no recursive separator.
(Actually, if you find Rogers hard going (it is!), and want something in addition to our slides as a warm-up to reading/understanding that, I commend to you as a source for examples regarding upper bounds in the arithmetical hierarchy lecture 35 (and in part lecture 36, which even does some hard completeness-proving, which most people think of as a type of lower-bound) of Dexter Kozen's book: Theory of Computation. In concept the book (electronic and as-a-book) is on reserve for our course, though I didn't check if the library actually did what I asked. Kozen is at an easier reading/understanding level than Rogers. But to avoid confusion beware: Kozen (in addition to other unusual notations you'll see in that reading) defines HP in terms of halting, not (as we do) accepting; but in our course we'll ALWAYS use the accepting-based notion.)
Note that the midterm was on October 20th, which gives you a sense of just how very much faster we have been moving this year than in that year, especially as I think that there isn't much, if anything, on this exam that you have not seen enough material so far as to be able to reasonably attempt the question.
Students had 75 minutes to take the exam.
So, if you would like to test yourself, take this (giving yourself just 75 minutes total). And then look at the answers, or work with a classmate in grading each other. If some problems seem particularly hard or confusing, then bring your questions in to the 9/28 Review Session, so that at that session the students and Ethan can jointly tackle any of these problems that you are particularly interested in.
And here is a related example/explanation that I sent to the TAs (it is a bit sloppy and not polished, but i was just trying to convey why i above said it will work up to poly): "For example, if we have say n^486 formulas, each of length at most say n^100, and each time we combine 2 objects the output is at most 486 times the sum of the lengths of the input formula-objects (it in fact is much less than a 486 factor under the combiner formula we discussed), then the length of the superformula that encodes them all, if we use the balanced tree approach, will be bounded by roughly about (n^100)*(972^{ceiling(486\log_2(n))}, and that is polynomial, namely, cheating and ignoring the ceiling: n^{100 + 486*log_2(972)}."
By the way, as to Conrad's question about whether all P-selective sets are about ordering, I point you to Section 2.2.2 of that book: "Are there P-selective sets other than standard left cuts?" It covers work showing that if P=PP, then EVERY P-selective set other than SigmaStar is many-one equivalent to a standard left cut. So, if you were to get your hands on even one P-sel set that you could prove is not m-equiv to any standard left cut, you would have separated P from PSPACE and would be crowned as the greatest computer scientist who ever lived. (Will that problem be given on a surprise quiz on Monday? Who knows...)
Useful Links:
Some of My Favorite Bits of Science Wisdom:
Other Odds and Ends (Mostly Quotations):