CSC286/486, Spring 2021

## CSC 286/486 - Computational Complexity

Instructor: Lane A. Hemaspaandra.

Course Information Document/Syllabus: Version 2.0.0.

Course Announcements/Library Reserves/Etc.: Reserves via Blackboard, Announcements (if any) mostly via Blackboard but also there may be Notes on this page in the Day-to-Day list.

Prerequisite: CSC 280/480.

• If you want to jump always directly to the end of the homepage (as most people seem to prefer to do in this course), which is where all the most recent stuff is, all you have to do is to bookmark the URL with EndOfPage label attached, namely, click this (note: it does not jump to the entire end of the page, but rather jumps to the very end of day-by-day log; so after jumping there, depending on your browser, you might want to scroll up to see the most recent additions) and then do an Add Bookmark. But, on the other hand, if you want to start at the start of the page each time, then click here and bookmark that.
• To help you immediately see the breaks between days, a UR yellowjacket will separate each day from the next in the day-by-day list below, and a team of four yellowjackets will separate the day-by-day list from the Useful Links/etc. that end this web page. What does a yellowjacket look like? For the purpose of this course, let it be this (or at times its mirror image):
1. Go to the Follow That Page web site.
2. Sign up there to track *exactly* the following URL (use the one below so that if your browser right now has a subarea or number or so on modifying the general page, you instead of putting that in as what should be tracked put in the pure page URL, which is the following; please be careful not to, due to problems with cut-and-pasting, put a blank space after the end of this URL when you paste it into Follow That Page as that may yield a confusing "Error 404"):
http://www.cs.rochester.edu/u/www/u/lane/=courses/=CSC486/index.html

### 2021/2/1

• Session Topic: (Fair?) Apportionment Algorithms for Legislative Bodies (and, Briefly, Power Indices). Did an in-class, nongraded, exercise on apportioning legislative (or other) bodies; the class on its own found the famous method proposed by Alexander Hamilton, which "respects quota" and was eventually adopted by Congress in 1792 as the method used to apportion the US House of Representatives (though as mentioned in class, there was drama before and after, and we in the USA now use a sliding divisor method, using geometric means as the rounding break-points).

### 2021/2/3

• Session Topic: Nonconstructive Definition (or Nondefinition) of NP-Completeness. Did an in-class, nongraded, exercises on the class of sets that are P-complete wrt $$\leq_m^p$$ reductions (equivalently, the class of sets that are NP-complete wrt $$\leq_m^p$$ if P=NP; gave the so-called nonconstructive "definition" of NP-completeness of A, which substitutes for the typical "hardness" conjunct the requirement "if $$A\in NP$$ then P=NP"; and let us call that notion NP-complete$$'$$; did an in-class, nongraded, exercises on whether NP-complete = NP-complete$$'$$, and went over an answer to that, which is that they are NOT equal, yet even knowing one specific set that is in one but not the other would tell you which way P vs. NP resolves and so would result in winning a Turing award (during this discussion, we mentioned but left to be proven in the future--it is now a take-home non-quiz exercise, though a very hard one---one element of that proof, namely Ladner's Theorem, i.e., "If $$P \neq NP$$ then there exists a set A such that A is in NP and not in P yet is not NP-complete);
• Non-Quiz Exercise: Ladner's Theorem. Try to on your own (working with your classmates is fine) prove Ladner's Theorem (see the day's description for its statement).
• In our Hemaspaandra-Ogihara textbook, read the "Invitation" subsection of the Preface. This will give you some insight into how I view complexity. (I believe the book is available free online via the library's web site.)
• This is definitely NOT required reading (so it is not due 2021/2/8 or ever). But simply as a pointer for anyone who might have found the apportionment issues discussed in the February 1 class interesting as to their history side (and as I said, I'm not at all a history professor), a *great* book (that covers the history and the methods and lots more, but isn't concerned with issues of computational complexity or power indices; for those, see the Fal-Hem or HRSZ papers I'll mention later in this entry) by two operations research professors, on that is the book "Fair Representation: Meeting the Ideal of One Man, One Vote," by M. Balinski and H. Young, Yale University Press. (If you doubt I was ever young, take a look in the acknowledgments section: When I was an undergrad, I did the (admittedly very, very simple) programming that generated the tables of Appendix B.) It is a very fun, readable book. If you want to see the models/complexity side of the notion we got to at the end, power indices, the strongest result currently on the complexity of the Shapley-Shubik power index was in the 2009 TCS paper "The Complexity of Power-Index Comparison" by Faliszewski and Hemaspaandra (though we're basically just strengthening by one notch a seminal classification done by Deng and Papdimitriou in their 1994 paper, "On the Complexity of Comparative Solution Concepts" on the journal Math. of O.R.), and as to heuristically computing power indices, as applied to the apportionment methods, see for example the old Journal of Experimental Algorithmics paper "Power Balance and Apportionment Algorithms for the United States Congress" by Hemaspaandra, Rajasethupathy, Sethupathy, and Zimand.
• Slides. Slides (that the few-week segment of the course that is about to start will use) are
• here in their original version (which is by far the better version for viewing on computer screens, and to use for color printers, and for projecting using projectors that can render well the light blue-gray used heavily on the first slide and then also in an number of the later slides, where it typically is used for Examples).
• here in a version where all the light blue-gray text has been digitally modified (although at the slight price of having the altered text come out a bit blurry) to be in a darker blue (this is usually the better version if you are printing on a black-and-white printer--most especially if you are printing 2-up or 4-up--or if you are projecting on a projector that can't display well light blue-gray text; do not use this if you are primarily going to view this on your computer's screen, as this is *not* good for that.

### 2021/2/8

• Session Topic: Syllabus and Introduction to the Course. Philosophy of the course (not just learn facts in a one-way stream, but rather we'll in large part work in a discovery-based fashion model, where you will be hands-on discovering proofs of many of the main results of complexity, usually working in teams); highlights of the syllabus such as a discussion of academic honesty and the flow of the term and the grading basis and chunks and dropping of chunks (but everyone is expected to read in full the syllabus before next class if you have not already done so).
• Read the entire syllabus. (Correction to something I said in class: I did *not* assign it as reading related to the 2/3 class; but it is assigned now.) The syllabus (course information document) is filled with information about the course and its nature and its rules and so on.
• Note: If you did not do the reading assigned last class (the Hem-Ogi "Invitation" subsection, of course read it now; but please do do all reading when assigned; I'll usually assume you have, and so won't include "reminder" bullets such as this one).

### 2021/2/10

• Session Topic: Various Notions of (or Arguably in Two Cases Perhaps Not of) Low Information Content. Tally sets; sparse sets; P-close sets (the class P-close); almost polynomial time sets (the class APT); near-testable sets (the class NT) and nearly near-testable sets (the class NNT); exercises including: proving that the two most common definitions of sparse sets in fact yield the same class as each other, proving APT $$\subseteq$$ P-close, and proving NT $$\subseteq$$ NNT; mentioned why NT can be brute-forced in PSPACE and briefly mentioned that it is in fact closely related to the class known as "ParityP" ($$\oplus$$P).

### 2021/2/15

• Session Topic: Turing Machines and Weaker(-Seeming) Models of Computation. Turing machine definition; 2 stacks = 1 tape; quick comments on why 2-dimensional tapes are no better than a 1-dimensional tape; pairing function (between pairs of integers, and the integers); counters and pebbles (e.g., and this was done as an in-class group-quiz, if we use a silently-bounce-off-of-it left-end wall then two pebbles can simulate two counters just fine).

### 2021/2/17

• Session Topic: Recursive Languages, Recursively Enumerable Languages, Enumeration Machines, The Halting Problem, and Diagonalization. Definition of the recursive sets and the RE (recursively enumerable, and we will see the robustness of the notion) sets; introduced Turing's "enumeration" Turing machines; proved that that the class of languages enumerated by enumeration Turing machines is exactly the class of languages accepted by (normal) Turing machines; in that proof, we saw the lovely, important notion of "dovetailing" computations; proved that an RE set can be enumerated in increasing order if and only if it is a recursive set; defined coRE; proved RE $$\cap$$ coRE = recursive (i.e., we showed that if L is RE and $$\overline{L}$$ is RE, then L is recursive); there is a universal Turing machine; definition of the halting problem; via a diagonalization proof proved that the halting problem is not coRE, and thus that the halting problem is not recursive (i.e., we proved that the halting problem is undecidable), and indeed (since we proved that $$\overline{HP}$$ is not RE) is not even coRE; the halting problem is RE.

### 2021/2/22

• Session Topic: Recursive Separability (and Nonseparability): Disjoint coRE Sets Are Always Recursively Separable, but Some Disjoint RE Sets Are Not Recursively Separable. As graded, in-class, group exercises, we covered these and their solutions: Disjoint co-r.e. sets are recursively separable (i.e., if A is a coRE set and B is a coRE set and $$A \cap B = \emptyset$$ then there is a recursive set C such that $$A \subseteq C \subseteq \overline{B}$$); there exists disjoint r.e. sets that are not recursively separable.

### 2021/2/24

• Session Topic: Undecidability via Many-One Reductions (Using Many-One Recursive Reductions as a Tool for Proving Undecidability: Tool A); Turing Reductions (Another Tool for Proving Undecidability; Tool B); Proving Non-RE-ness and Non-coRE-ness (Via Many-One Recursive Reductions; Tool C). Many-one reductions; many-one reductions as a tool for proving undecidability (Tool A); used the tool to show a set (having to do with machine-index and input pairs on which the machine with that index halts on the given input) to be undecidable, via providing a recursive many-one reduction from HP to it; Turing reductions; Tool B; many-one reducibility for a pair of sets implies Turing reducibility, but sometimes not the other way around; Turing reductions as a tool for proving undecidability---if A recursively Turing reduces to HP, then A is undecidable; proved that the index set $$L' = \{i~ | ~L(M_i) = \emptyset\}$$ is coRE but not recursive (or RE); proved that the index set $$L'' = \{i ~|~ L(M_i) = \Sigma^\star\}$$ is not recursive; any set that many-one reduces to an r.e. (respectively co-r.e., recursive) set is itself r.e. (respectively, co-r.e. (I didn't explicitly prove the co-r.e. case in class, but it is clearly true from the r.e. case plus the definition of co-r.e.), and that fact, which we stated and (in words) proved, gives a tool (Tool C) that can be used to prove sets non-RE and non-coRE; as a first example of how to use the new tool, we used it to prove that the index set $$L'' = \{i~ |~ L(M_i) = \Sigma^\star\}$$ is neither r.e. nor co-r.e.; also argued that that {i | $$L(M_i)$$ is infinite} is neither r.e. nor co-r.e.; Rice's Theorem for recursive index sets; discussed how Rice's Theorem must be used very carefully, e.g., it regards the languages that machines accept, not the details of their running such as whether the run for an even number of steps or whether they end in the lexicographically smallest state; mentioned and flashed up for a moment on the slides Rice's Theorem for r.e. index sets ("Rice II").

Please review all the slides we covered in class today (since reviewing what was covered is implicitly a reading/study assignment after each class, I typically won't explicitly list it, though for today, as an example, I just did); we covered a lot of material, some of it quite quickly.

Reminder: Please do make sure you understand exactly what HP is defined as; we'll be consistent regarding that through all our slides.

If you want examples of proving things undecidable, any standard textbook (but avoid Sipser for this as he uses a different notation) will have examples, but the most in sync with my approach (as long as their proofs don't make you think that pictures suffice as proofs) is Hopcroft-Ullman-1979.

### 2021/3/1

• Session Topic: Immunity and Bi-immunity; Reductions, Completeness, and Oracle TMs; the Kleene Hierarchy. Last class's quiz was on the fact that there is an set that has no infinite RE subsets (i.e., there is an RE-immune set), and via BB Announcement I distributed a solution; and today's quiz was on the fact that there is an RE-bi-immune set (a set such that neither the set nor its complement has an infinite RE subset), and we sketched the answer in class after the quiz; some types of reductions between problems (reviewed again), including many-one and Turing reductions; oracle TMs; complete sets; gave a (so-called universal) complete set for the class of RE sets, and proved that it is indeed RE-complete; definition of the classes Sigma_k, i.e., the levels of the Arithmetical Hierarchy (aka, the Kleene Hierarchy, aka the Arithmetic Hierarchy, aka the Kleene-Mostowski Hierarchy); definition of the classes Pi_k; the oracle definition versus the quantifier characterization of the levels of the arithmetic hierarchy.

### 2021/3/3

• Session Topic: UR Study Break Day (No Classes).

### 2021/3/8

• Session Topic: The Kleene Hierarchy and the Tarski-Kuratowski Algorithm, and Our Start on Complexity. Proved why (for the case of Sigma_2) the machine-based definition and the quantifier-based definition yield the same class as each other; in doing so, we gave a definition of k-simulations; a universal set for Sigma_2^0 (don't be freaked by the zero---we've been suppressing it in class as implicit, so it doesn't mean anything important for us); hierarchy structure of the Kleene Hierarchy; some examples of natural sets in different levels; the Tarski-Kuratowski algorithm (or... counting quantifier alternations gives upper bounds; the term "Tarski-Kuratowski Algorithm" refers to the process of unwinding down to a bunch of alternating quantifiers on top of a recursive predicate... it isn't really at all an utterly clean, mechanical "algorithm" in the standard sense, but nonetheless, it is routinely described as the "Tarski-Kuratowski Algorithm"); examples of using the Tarski-Kuratowski Algorithm, in particular, we showed that {i | L(M_i) is finite} is in Sigma_2^0, that {i | L(M_i) is infinite} is in Pi_2^0, and that {i | L(M_i) is cofinite} is in Sigma_3^0; showed a quick chart showing a list of where certain things can be proven to fall; universal sets; complete sets (just to be explicit: for any class C, we say a set A is complete for the class C (with respect to many-one recursive reductions) exactly if it holds both that A belongs to C and each set B\in C satisfies B \leq_m A); went over the top-level part of the proof that {i | L(M_i) is finite} is Sigma_2^0 complete, but left for you to read from the slides the key proposition within that, namely, that the universal set for Sigma_2^0 many-one recursively reduces to that set; went briefly over an example that if one is not careful might seem to just be put into Pi_5^0 by Tar-Kur, but that with a certain insight Tar-Kur can put even into Sigma_4^0; discussed three different methods we now have regarding how to prove that a given set is not RE; DTIME; NTIME; P; NP.
• Pointers to Reading/Literature (some required, some not).
• (Not required) There is no satisfying, easy-level literature source (partial exception: see the Kozen pointer below) for the Kleene Hierarchy (which we discussed today) and the Tarski-Kuratowski Algorithm (which we also covered today). Sections 14.1/14.2/14.3/14.8 of the (not easy) book by Rogers, "The Theory of Recursive Functions and Effective Computability," are as close as one gets, in the literature, to a satisfying yet readable presentation of this. But among those sections, let me particularly stress that you may find Section 14.3 to be very valuable. So, you might want to look at Section 14.3 there, as it makes very clear how Tarski-Kuratowski goes, and it is important that you know how to do the Tarski-Kuratowski quantifier revealing/counting process (it is not impossible that that skill might be one of the things called upon in a future graded exercise).

(Actually, if you find Rogers hard going (it is!), and want something in addition to our slides, 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. (I think the library may well have it electronically, which is useful in these crazy times.) 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.)

• Comment on the Nature of Problem Solving (and Doing Reductions). Solving problems, and in particular let's speak about finding reductions, is not a mechanical process in which one tries a list of things that have worked before and then quits if none of them works... admittedly, sometimes a "stock" reduction may indeed work (and if so, great!), but other times one has to vary a previous reduction or even think of a completely new approach... in doing this, it is typically best to be guided by the goal, namely, to realize that to many-one reduce from A to B one needs a mapping that is recursive and that maps from elements of A to elements of B and from elements of \overline{A} to elements of \overline{B}, and then to---by trial, error, intelligent adjustment and construction, etc.---build a reduction function that accomplishes this (and then to prove that it is indeed does the desired reduction).
• An Example of a Reduction. Let us quickly describe a reduction that shows that $$A \leq_m B$$, where $$A = \{ \langle i,j \rangle {}~|~ L(M_i)=L(M_j)\}$$. $$B = \{i ~|~ M_i \mbox{ is total}\}$$. WAIT! FIRST, PLEASE, YOURSELF, SPEND SOME TIME WORKING ON THIS (to better master reductions...). And then, after you (ideally) solve it, or give up (but I hope you'll solve it), then look at my answer sketch here. Our reduction is defined as follows. Let sigma(\langle i,j \rangle) output the index of a Turing machine that on arbitrary input y does the following: It simulates an enumerating TM for L(M_i) for |y| steps. Then for each string enumerated during those steps, it runs M_j on that string to make sure it halts and accepts (if not, we make sure to run forever). If so, then it simulates an enumerating TM for L(M_j) for |y| steps. Then for each string enumerated during those steps, it runs M_i on that string to make sure it halts and accepts (if not, we make sure to run forever). If we get to this point, then we halt. Note that sigma is recursive. Note that if \langle i,j \rangle is in A, then sigma(\langle i,j \rangle) is the index of a Turing machine that halts on each input (i.e., is a total TM), because each bunch of things enumerated by one in |y| steps must be in the other's language, since they are the same language. Note that if \langle i,j \rangle is not in A, then sigma(\langle i,j \rangle) is the index of a Turing machine that is not total; in particular, let x be the first string that is in exactly one of L(M_i) and L(M_j). Then when this is enumerated by one of the enumerators, it will not be seen to be in the language of the other, and so the machine will not halt on ANY y long enough that we have x enumerated in our process, so it is in fact not just not total, but it indeed halts on just a finite set of inputs. This completes the reduction.
• Suggested Self-Study Exercises. [If you want additional practice on Tar-Kur, here are two problems you could try. If you can't do them, please discuss them with your take-home exercise's groupmates, or ask Sid or me during an office hour. This suggested exercise will not be collected or graded.] (a) Prove that { $$i~ | ~L(M_i) = \emptyset$$} is in $$\Pi_1$$. (b) Prove (directly by Tarski-Kuratowski; not by getting it indirectly from the Tarkski-Kuratowski study of "cofinite" on our class slides) that {$$i ~|~ L(M_i)$$ is coinfinite (i.e., $$\overline{L(M_i)}$$ is infinite)} is in $$\Pi_3$$.

### 2021/3/10

• Session Topic: NP, NP-Completeness, the Polynomial Hierarchy, UP (the unambiguous version of NP), $$\bf UP_{\leq k}$$ (the bounded-ambiguity generalizations of UP), Constant-Ambiguity Nondeterminism and Unambiguous Nondeterminism Stand or Fall Together as to Equality with P. The polynomial hierarchy, and why it is in some ways analogous to the Kleene hierarchy; mentioned briefly that one can pair clocks with NPTMs in such a way as to convert nasty enumerations into nice ones in which we know that the i'th machine runs in NTIME at most $i + n^i$; polynomial-time many-one reductions; NP-completeness; "co" classes; coNP; a universal NP-complete set; NP characterized; Cook's Theorem, a gateway for proving NP-completeness; discussed the standard (many-one reduction) tool for proving NP-completeness; gave some examples of NP-complete sets; UP; UP_{\leq k}; the class was asked as an exercise to prove that for P = UP iff P = UP_{\leq 486} (and I mentioned that there is nothing special about 486---it holds for each k \geq 1); mentioned briefly in passing that, for each k \geq 1, it holds that k-to-one one-way functions (you can find the precise definition of complexity-theoretic one-way functions in our Hem-Ogi book, in the same chapter that has a proof of the UP_{\leq 2} result the class proved today, but you don't have to read that at this point) exist if and only if P \neq UP_{\leq k}; and so what your proved in class today (or to be more precise, what you proved if you did not just the 486 class but the generalization to all "k") in fact shows that one-one one-way functions exist if and only if it holds that for each k \geq 1 at-most-k-to-1 one-way functions exist, or put another way and more informally, unambiguous one-way functions exist if and only if bounded-ambiguity one-way functions exist (one direction is trivial but the other is surprising at first... but the class in effect sought to prove it today via (if supplemented with the above-mentioned relationships between classes and one-way functions, which we have not proven but is true), with luck, noticing the key insight, namely, isolating out the most extreme ambiguity by making a set consisting of the points it is met on and then using the fact that THAT set is a UP set, and so is a P set, and then building the P-ness of that set into a machine that deterministically knows if the extreme case holds and so if it does we know what to do already and if it doesn't hold, we can in a protected-from-the-extreme-case way do a simulation, and we can argue that that gives us (a UP algorithm for the set in the 2 case and more generally, and this is used inductively in the higher cases) a UP_{\leq k-1} algorithm in the k case; see the Hem-Ogi book's proof, which I've assigned as reading, for more details).
• Reading (due 2021/3/15/2pm but you actually should do it now as it is the answer to the in-class exercise you just did today). New reading: In our Hemaspaandra-Ogihara textbook, read from line negative 3 of page 35 through the QED box 3/5 of the way down page 36. That precise segment of reading will show you the proof of what we were doing in class, for the general case of k, but will avoid you having to at this moment learn about 1-way functions, since that segment is all in the language of complexity classes. P.S. Reading reminder: If you didn't do the required part of the due 2PM 3/10 reading yet, (obviously) please do it right away.

### 2021/3/15

• Session Topic: How Parameters Can Interact with NP-Completeness; the Borodin-Demers Theorem. Reviewed in detail the proof of Watanabe's result that constant-ambiguity nondeterminism and unambiguous nondeterminism stand or fall together as to equality with P; looked at a problem, with a parameter, that for small values is in P, but for large values is NP-complete; showed how to make sure that Cook's reduction reveals, in the output formula, the machine and input that the formula is about (i.e., superCooking Cook); proved the Borodin-Demers Theorem (let me here mention one heads-up as to a possible confusion: sometimes, people thing "oh, the elements of the Borodin-Demers set must all be tautologies"; but that is not good reasoning; rather, the elements of the Borodin-Demers set, i.e., the elements of the S of the proof, are all *satisfiable*, as Borodin-Demers promises and delivers that, but they may not be tautologies, since for example variable assignments that in effect represent illegal instantaneous description changes between one step and the next in the machine flow that the formulas are capturing about the actions of the NP machines in input x will be such that under those assignments the formula evaluates to False).

### 2021/3/17

• Session Topic: Truth-table and Turing Reductions. Truth-table reductions; Turing reductions; quiz (to be gone over next class) on proving that $$P_{tt}^{NP} = P^{NP[O(log n)]}$$.

### 2021/3/21

• Session Topic: Tightening a Parallel to Serial Simulation via Mind Changes. Went over the class's proof that $$P_{tt}^{NP} = P^{NP[O(log n)]}$$; noted that the proof in fact establishes that that $$P_{(2^k - 1)-tt}^{NP} \supseteq P^{NP[k]}$$ and that $$P_{(2^k - 1)-tt}^{NP} \subseteq P^{NP[k+1]}$$; tightened this to Beigel's result $$P_{(2^k - 1)-tt}^{NP} = P^{NP[k]}$$ by using Markov's notion of mind changes to binary search not over census values but rather over number of mind changes. (Side note (note: the papers mentioned here are not required reading): And that is as good as one can get, short of collapsing the polynomial hierarchy; that is, if either direction of the containment can save even one query, that would collapse the bounded query hierarchies, which by work, in the journal SIAM J. Computing, of Kadin---if you look at it make sure to look at its Erratum that appeared 3 volumes later, and also the work, 8 years after the original paper, in the same journal, of Chang and Kadin, or see the survey "What's Up with Downward Collapse" in SIGACT News by Hemaspaandra, Hemaspaandra, and Hempel to survey the long line of related work on Boolean hierarchies over levels of the polynomial hierarchy---is known to collapse the polynomial-time hierarchy... though not necessarily to as deep a level as one might hope.)

### 2021/3/24

• Session Topic: Self-Reducibility, SAT, Search to Decision, Levin's Amazing Insight. Self-reducibility of SAT, in particular, the fact that SAT is 2-dsr (2-disjunctive, polynomial-time, self-reducible); that means that that if $$F(x_1,....,x_k)$$ is a propositional Boolean formula and k \geq 1 and each of the k variables actually occurs at least once in F, then it is true that: $$F(x_1,....,x_k) \in SAT$$ IF AND ONLY IF $$(F(TRUE,....,x_k) \in SAT$$ OR $$F(FALSE,....,x_k) \in SAT)$$; how that allows us to efficiently reduce SAT's search version to its decision version; as a semi-quiz, asked the following (it might at first seem that doing this is impossible, but Leonid Levin--one of the creators of NP-completeness--by a lovely argument line showed that this IS possible to do, right now, today): Write, right now, for real, a (single) program G (the problem is NOT asking you to merely claim/prove that such a program G exists... you need to GIVE such an actual program) such that the following is provably (by which I mean YOU can, right now, prove it, without waiting for the P vs NP issue to be resolved) a true statement: "If P=NP then (\exists polynomial p)(\forall F \in SAT)[G on input F outputs a satisfying assignment of F within p(|F|) steps]."

### 2021/3/29

• Session Topic: FewP, Few, #P, $$\bf\#_{few}P$$, Lowness, the Power of ParityP (and the Iterative Constant-Setting Technique). Representing NP and UP and UP_{\leq 3} as leaf languages (briefly); $$\rm \oplus P$$; FewP and Few; #P and $$\rm\#_{few}P$$; relationship between complete sets and having constructive programming systems (briefly mentioned); proof that $$\rm NP^{NP \cap coNP} = NP$$; proof by iterative constant-setting that $$\rm Few \subseteq \oplus P$$ (an immediate corollary of that result is that $$\rm FewP \subseteq \oplus P$$, but we also explicitly gave a direct proof of the latter, basically, via guessing every (ordered) subset, except the empty set, of the set of accepting paths of the few machine---in class, I phrased it still in terms of the coefficients, but one can equivalently view it just as guessing uniquely every subset of the set of accepting paths other than the empty set of accepting paths, and by the sum-of-binomials issue mentioned in class, that is establishes it); gave as a home exercise: prove $$\rm P^{NP \cap coNP} = NP \cap coNP$$ but NOT via the standard approach that is a simplified version of our proof that $$\rm NP^{NP \cap coNP} = NP$$, but, rather, by showing that the latter itself easily implies the former.

### 2021/3/31

• Session Topic: Start of the project; Levin's Insight (continued); Ladner's Theorem. Went over the nature of the project (more will be posted on that soon either via the syllabus or via a BB posting); went over the class's correct proof, which was a semi-quiz, of the Levin insight/claim from last class (note: the way I stated it on the web site last class did NOT require that L(G)=SAT, so that fact that the class's solution didn't address the case of inputs not in SAT was not at all a problem relative to the statement I had given; however, as per the discussion in class today, one can by adding the brute-force fallback even show the slightly stronger results that one can even write, right now, today for real, a (single) program G (the problem is NOT asking you to merely claim/prove that such a program G exists... you need to GIVE such an actual program) such that the following is provably (by which I mean YOU can, right now, prove it, without waiting for the P vs NP issue to be resolved) a true statement: "(L(G) = SAT) AND (if P=NP then (\exists polynomial p)(\forall F \in SAT)[G on input F outputs a satisfying assignment of F within p(|F|) steps])"; stated Ladner's Theorem (namely, "If P \neq NP then there is a set A such that A \in NP, A \not\in P, yet A is not NP-complete"), and gave a hint of what two infinite lists of "requirements" might be a good path toward resolving it---proving the theorem is a group-of-the-whole semi-quiz due for class on Monday.
• Presentation Project. As a item that will count as 5 100-point chunks, superchunked (see the course information document for what that means), everyone who was in class today or on at least one of the half dozen previous class seesions was assigned to one of two groups (group Chapter 3, which is Benjamin Carleton, Evan Cohen-Doty, Weiwei Gu Mandar Juvekar, Jialin Li, Conor Taliancich, and Melissa Welsh, and group Chapter 5, which is Adam Dees, Aaron Gindi, Arian Nadjimzadah, and Patrick Phillips). If you missed today and all of the past half dozen class sessions, I'll assume unless I hear otherwise that you are not taking the course or are not doing the course's material, and so do not want to do this project, and so unless you contact me by a week from today (April 7) asking to do this project (in which case I will assign you a project and talk date(s)), your project grade will be a zero.

In you group, you will master one chapter (the one that is the name of your group) of the Hem-Ogi textbook and prepare slides for and present as the April 12/14/19 lectures (if group Chapter 3) or as the April 21/26 lectures (if group Chapter 5) your slides on and lectures on that chapter. You do not have to cover the entire chapter. Each group should choose for itself the "right" amount of material from the chapter so that you fully fill your number of lectures, and cover clearly the part of the chapter's material that you choose to cover.

You WILL be graded on the quality of your entire unit (and that grade will be shaped by both the quality of the slides and the quality of the presentations, though those won't get separate grades from each other, probably). Some time after your final talk, after Sid and I have had time to talk with each other, so perhaps that evening or a day later, you'll meet with Sid and me for our feedback and to get your grade.

The details on how/what you'll hand in and do are as follows:

I'll assign the grade to your talk/slides (the ones presented in class), but will consult with the TA when doing so to get his input as to what he thinks of them.

### 2021/4/5

• Session Topic: Relativization: P vs. NP (and more). Relativization and its meaning/role (if we show conflicting relativizations regarding a potential equality, that means the issue cannot be resolved in either direction by any relativizable proof technique); showed that there is a relativized world (namely, use any PSPACE-complete set as the oracle) in which P=NP; showed (by diagonalization) that there is a relativized world in which P \neq NP and indeed in which P \neq UP; sketched the flavor of the proof (using the Party Lemma from the J. Cai, T. Gundermann, J. Hartmanis, L.~Hemachandra, V. Sewelson, K. Wagner, and G. Wechsung, Boolean Hierarchy work---that was a 2-paper series in SIAM Journal on Computing appearing in the December 1988 and February 1989 issues; we didn't state or prove the lemma in class; the party lemma was used there to do relativizations of the Boolean Hierarchy over NP) that there is a relativized world in which UP_\leq1 \neq UP_\leq2 (a result first obtained in Beigel's 1989 IEEE Structure in Complexity Theory Conference paper).

### 2021/4/7

• Session Topic: Ladner's Theorem/Delayed Diagonalization; A World Where P \neq NP = coNP . Proved Ladner's Theorem (namely, if P \neq NP, there there is a set A such that A \in NP-P yet A is not NP-complete); proved that there is a relativized world in which P \neq NP = coNP, and indeed, in which P \neq UP \cap coUP = PH = PSPACE (with the model of relativized PSPACE being that he query tape also obeys the polynomial space bound).
• Optional Reading. It may be hard to get to some of this reading, and if you followed the in-class proof it may not be needed anyway. But fyi, here are some sources for the proof of Ladner's Theorem, or of generalizations of it.
• Ladner's Theorem is Theorem 4.8 of the book Theory of Computational Complexity by Du and Ko, and the book includes a proof.
• Ladner's own paper is "On the Structure of Polynomial Time Reducibility", and appeared in Journal of the ACM in 1975, Volume 22, Number 1, pages 155-171.
• For a tutorial presentation (written in honor of Prof Ladner, on the occasion of his retirement) of a slightly stronger result than "Ladner's Theorem," that in fact was also obtained by Ladner himself in his seminal paper, one can look at "Team Diagonalization," L. Hemaspaandra and H. Spakowski, SIGACT News, V. 49, #3, pp. 51--61, September 2018.
• More Optional Reading. The first person to show that there was a relativized world in which P \neq UP \intersect coUP = coNP = NP = PH was Rackoff, who achieved that in his paper in Volume 29, Issue 1 of Journal of the ACM (his abstract doesn't quite say that it does this, and uses an older notation, but since coUP \subseteq coNP and he also for his oracle shows coNP \subseteq UP, he has UP=coUP, and so his P \neq UP in fact is the same in that context as P \neq UP \intersect coUP (since UP = coUP).

### 2021/4/12

• Session Topic: Chapter 3 (P-selectivity and Tournaments), Lecture 1 (of 3). Tournaments; the existence in tournaments of log-small superloser sets; P-selective sets; NPMV functions; NPSV functions; nondeterministic selectivity (esp., NPSV-selective sets); sparse sets; P/poly (small circuits); P^{SPARSE} (which equals P/poly, though this was not proven in the lecture); P-sel \subseteq P/poly; left cuts of real numbers; the fact that the left cut of any real number in (0,1), even an undecidable one, is P-selective, and the fact that follows from that that there are undecidable P-selective sets... so P-selective sets are, information-wise, polynomially close (per length, so to speak) to P, yet can be undecidable (or in fact even beyond the entire Kleene Hierarchy)... P-sel functions differently regarding different measures of hardness!
• Optional Reading. Group "Chapter 3" did not send any reading assignment yet. But FYI, much of what was covered is in Chapter 3 of our textbook (available free online via the UR library); and also, fyi, there is an entire book on selectivity theory, namely, "Theory of Semi-Feasible Algorithms" by L. Hemaspaandra and L. Torenvliet (though it is not free online but is currently, as a physical book, in the UR Carlson library).
• At-Home Reading Exercise (counts as a quiz). As a 4/12 quiz, you must by 11:59PM EDT on Thursday April 15th watch (live or taped---more on that later) me give a lecture on the paper "The Complexity of Online Bribery in Sequential Elections" by E. Hemaspaandra and L. Hemaspaandra and J. Rothe (TARK 2019, plus there is a 40-something page tech report at arXiv.org). To prove that you have watched it, you must by that time email to csc486staff "at" cs.rochester.edu, with the subject field exactly "Quiz submission/credit request for 4/12 quiz" an email that states roughly what I refer to in the talk by the phrase "fully vaccinated formula" (note: the phrase does not appear in either of the paper's printed versions or on the slides or in the video part of the recording, but it *is* in my spoken delivery of the talk; we are NOT grading you regarding this on the technical perfection of your expression of what I mean by the phrase, esp. as in the talk I don't really formally define it; but you do need to tell enough about what I said that Sid is convinced that you did listen to the video, rather than sending in a---quite hard to do and get it right--guess of what the phrase means). Then Sid (if your answer meets the bar just mentioned) will give you a 100-percent credit for it in the Grade Center column "4/12 Take-Home Quiz-Exercise (Online Bribery)"; please make sure to check that column Friday afternoon (4/16), so you can on Friday afternoon let Sid know if you emailed for quiz credit yet it was not recorded in that column. If you don't meet that bar or don't send the email in time, Sid will assign you a zero on this quiz.

You have two possible paths to watch the talk.
(a) One path is to watch it live, when I give it at 12:20PM on Wed., April 14, at Theory Canal. (But as that is via Zoom, and you'll need to get the Zoom link. I don't want to post that on the web, but I will send it to you via BB announce on the evening of 4/12, and so it will be in BB on our announcements page's listing of such.
(b) The other path is to view the recording of my March 19th 2021 talk on this paper at the New York Colloquium on Algorithms and Complexity (NYCAC 20-21). That is currently being added to our course in Panopto, as the file/video "2021-04-12-quiz-and-talk-Online-Bribery-NYCAC-20-21-Lane-Hemaspaandra-20210319-1555-5" (it is a .mp4 file). There is no natural place for us to link to it from in our BB area, so I've linked to it from our "CSC 286/486 main-class-session recordings" page, though it in fact is not a main-class-session record. So, there, you will have THIS quiz/video (listed under 4/12), and will, when Sid posts it, also have the 4/12 in-class lecture by group Chapter 3.

### 2021/4/14

• Session Topic: Chapter 3 (P-selectivity and Advice), Lecture 2 (of 3). P-sel \subseteq P/quadratic; P-sel \subseteq PP/n+1; tournaments have kings; P-sel \subseteq NP/n+1 (indeed, even using just a linear number of nondeterministic bits) but P-sel $$\not\subseteq$$ NP/n.
• Optional Reading. Group "Chapter 3" did not send any reading assignment yet. But FYI, in case you want it in a textbook form, much or all of what was covered is in Chapter 3 of our textbook (available free online via the UR library). online but is currently, as a physical book, in the UR Carlson library).
• Reminder Regarding the At-Home Reading Exercise (counts as a quiz), and a New Option. Keep in mind the 4/12 take-home quiz/exercise is due by 11:59PM EDT on Thursday April 15th; see the 4/12 entry for more details of what you need to do. Also, there is a new path to doing this. The 4/14 Theory Canal version of the talk was also recorded, and probably by 1159PM on 4/14 it will be linked to from our BB area, in the same subfolder as the NYCAC version of that talk. The new version has the name "2021-04-12-quiz-and-talk-Online-Bribery-Theory-Canal-Lane-Hemaspaandra-20210414-1220.mp4." However, the NYCAC version quite likely is a better giving of the talk, as the 4/14 version was a bit rushed at the end. You can view either, or can have viewed the live presentation on 4/14; but please don't forget to send the required answer/mail regarding "fully vaccinated formula."

### 2021/4/19

• Session Topic: Chapter 3 (P-selectivity and Advice), Lecture 3 (of 3): Unique Solutions Collapse the Polynomial Hierarchy. Nondeterministic selectivity; is there an NPSV (NP single-valued) "refinement" of f_{SAT}, i.e., does some NPTM exists that for each unsat formula has no outputs and that for each sat formula outputs exactly ONE satisfying assignment (though it might be output by multiple paths), or, equivalently, does every NPMV function have an NPSV refinement?; well, it was shown in class that if that holds then the polynomial hierarchy collapses (in particular, it collapses the polynomial hierarchy to ZPP^NP, and in class the slightly weaker collapse to NP^NP was proven, and it was briefly mentioned in comments, even to S_2^{NP intersect coNP} (note: S_2^{NP intersect coNP} \subseteq \Sigma_2^p, and that inclusion itself relativizes); the proof went in two steps, with a key lemma being that NPSV-sel \cap NP \subseteq (NP \cap coNP)/poly.

### 2021/4/21

• Session Topic: Chapter 5 (Witness Reduction/Closure Properties), Lecture 1 (of 2) Chapter 5.1-5.2: Feasible closure properties; #P is closed under proper subtraction iff UP = PP; #P is closed under proper subtraction iff it is closed under all feasible closure properties; the analogous claim holds also for integer division.

### 2021/4/26

• Session Topic: Chapter 5 (Witness Reduction/Closure Properties), Lecture 2 (of 2) The rest of Chapter 5, esp. intermediate closure properties (such as proper decrement and integer division), though also issues regarding OptP and SpanP.
• Video on NFA Equivalence via QBFs (counts as a quiz). View David's talk on NFA Equivalence via QBFs (available in our BB area) in full, and extract the secret code, and email it in, all before noon on 4/28 to get credit for this quiz; a BB Announcement posting gives all the details.

### 2021/4/28

• Session Topic: The Strong Exponential Hierarchy Collapses. Exponential time classes; why building an "exponential hierarchy" by stacking exponential-time classes would result in a hierarchy that provably (by the deterministic time hierarchy theorem) did not collapse, and why for PH one CAN stack P/NP classes in building the hierarchy (namely, the magic is that polynomials are closed under composition but compose two exponential-time functions and it can be "hello double-exponential time"); the strong exponential hierarchy and the fact that it collapses via first proving that P^NEXP = NP^NEXP (equivalently, P^NE = NP^NE, since by padding the difference can be shown to make no difference) and then that itself inductively collapses the hierarchy to P^NEXP.
• Optional Reading. You don't have to read the following, but fyi, the SEH collapse result (and many more general things) was obtained in my JCSS Volume 39 paper "The Strong Exponential Hierarchy Collapses," although I think the proof there is a far harder, worse one than the one I used in class (mostly pointlessly harder, except that that paper is trying to get all sorts of additional results that actually themselves do seem to need the more painful method, so I suppose there was a point).

### 2021/5/3

• Session Topic: Summary of Course and Goals; also, Padding and Translations of Inequality. Summary of course and goals; P^NE = P^EXP (done as quiz); padding; NP-P contains tally sets IFF E \neq NE; stated, for work on proving between now and next class, this theorem of Hartmanis, Immerman, and Sewelson: NP-P contains sparse sets IFF E \neq NE (the "if" direction follows from the previous tally theorem, but the "only if" direction takes a lovely coding twist); I briefly summarized the course's content coverage (the things we covered) but also its point/goal, which to me is in fact more important than the specific content coverage (though the topics and results covered are indeed very important); in particular, the to-me-most-important goal of the class was to give you the chance to, and practice in, doing hands-on proving (and formulating), and most particularly, by doing so, to improve your ability to look critically at other's work (looking for errors, or missed directions, or new extensions), but even more so, to be able to look critically at your OWN work, so that you yourselves, every time you prove/formulate/state something will give yourself a referee report that, often, will remove errors, or even if there are no errors, may point you to an even simpler or better approach, or a stronger result.

### 2021/5/5

• Session Topic: Sparse Sets in NP-P. The Hartmanis-Immerman-Sewelson Theorem: NP-P contains sparse sets only if if E \neq NE.
• Bye! It was a real treat and delight (Zoom-)meeting each of you and teaching this course; thank you so very, very much for your hard work. And, just to reiterate (because it is a pretty important point) what I also tried to mention on Monday in class: as you know, the course covered various specific material (self-reducibility, problems, classes, recursive enumerability, diagonalization, immunity and bi-immunity, undecidability, the arithmetic hierarchy and upper-bounding using quantifier structure, NP, reductions, completeness, the polynomial hierarchy, fair apportionment (on day 1!), nonconstructive nondefitions of NP-completeness (on day 2!), notions of low information content (on day 3) such as APT/P-close/sparse/tally/etc., adaptive vs. nonadaptive access to NP and the trade-offs as to number of queries, census functions, mind changes, the Borodin-Demers Theorem, UP (unambiguous NP) and bounded ambiguity variants of NP ($$\rm{}UP_{\leq k}$$), your project material (on Chapters 3 and 5), NP-lowness of NP intersect coNP, FewP \subseteq ParityP, Ladner's Theorem and delayed diagonalization, relativization, P-selectivity and tournaments, padding, the strong exponential hierarchy's collapse, and much more), and I hope those pieces of knowledge will at times prove useful in your future career, e.g., when you want to classify the complexity of new problems that during your research pop out and say hello to you. But aside from that, I more generally hope that the broader flavor of this course---trying to rigorously capturee notions and trying to stress hands-on *proving* (often with collaborators) things about them, while trying to be so mentally focused as to always be looking for flaws in (others', but also) one's own proof lines (as well as looking for simpler proofs, generalizations, etc.)---will be something that will be useful to you during your careers in computer science (or beyond). Warmest thanks, and wishing you each a great career and, more immediately, successful finals, a safe and wonderful summer.

• Assistance Services (now renamed CETL, which provides a wide range of services including Disability Support).
• The DBLP Computer Science Bibliography.
• Department, URCS.
• RSI Information.

Some of My Favorite Bits of Science Wisdom:

• After solving a challenging problem, I solve it again from scratch, retracing only the *insight* of the earlier solution. I repeat this until the solution is as clear and direct as I can hope for. Then I look for a general rule for attacking similar problems, that *would* have led me to approach the given problem in the most efficient way the first time. -- Robert Floyd
• In computer science, elegance is not a dispensable luxury, but a matter of life and death. -- Edsger Dijkstra
• Imagination is more important than knowledge. -- Albert Einstein
• They are ill discoverers that think there is no land, when they can see nothing but sea. -- Francis Bacon

Other Odds and Ends (Mostly Quotations):

• I don't believe it. Prove it, and I still won't believe it. --Life, the Universe and Everything
• It was mentioned on CNN that the new prime number discovered recently is four times bigger then the previous record.
• Sooner or later society will realize that certain kinds of hard work are in fact admirable even though they are more fun than just about anything else. -- Donald E. Knuth
• Getting tenure doesn't really change anything. However, not getting tenure changes everything.
• My late friend Stan Ulam used to remark that his life was sharply divided into two halves. In the first half, he was always the youngest person in the group; in the second half, he was always the oldest. There was no transitional period. -- Gian-Carlo Rota, "Indiscrete Thoughts"
• Fools ignore complexity. Pragmatists suffer it. Some can avoid it. Geniuses remove it. -- Alan Perlis, Epigrams in Programming
• More Quotes from Dijkstra:
* None of the programs in this monograph, needless to say, has been tested on a machine. (From "A Discipline of Programming.")
* Computer science is not about computers, any more than astronomy is about telescopes.
* The question of whether computers can think is just like the question of whether submarines can swim.
• "Supposing a tree fell down, Pooh, and we were underneath it?" [said Piglet.]
"Supposing it didn't," said Pooh after careful thought.

Page Maintained by: Lane A. Hemaspaandra