The following are a few selected questions that students asked me by email. The students questions/comments are enclosed in asterisks *****. My answers follow. ************************* QUESTION In slide 18 of chapter 1, shouldn't it say 8 states (q0..q7)? *************************************** No! Have a look at definition 1.1 (Slide 8), where we define the number of states. Different people do it differently. One can argue, of course, that there are 8 states. But the start state is always there, so there is no TM with 0 states (should we use this interpretation). So often, the start state is not counted. A TM in our terminology with 0 states exists: it just has the start state q0. But there are many variations out there. Keep looking for any inconsistencies, I appreciate that. ************************* QUESTION I was just wondering if we will get any handouts for this course. *************************************** No, there will be no handouts other than the slides (they are on the webpage, both in ps and pdf format). The ps format prints better. The idea is that the slides are enough to get through. They are written in a way that they should be sufficient for you, provided you are attending the lecture. I am giving enough explanations in the lectures to understand the slides (well, I hope). ************************* QUESTION 1. what is the difference between countably many and uncountably many? *************************************** A set is countable if it has as many elements as there are natural numbers: i.e. there is a bijective (one-to-one) mapping between the natural numbers and this set. A set is uncountable if there is no such mapping. Both definitions are on the slides. The set of all subset of the natural numbers is uncountable. The proof is on one of the slides. ************************* QUESTION 2. how many Ids depends on tape symbols? *************************************** I do not understand this question. It does not make sense. ************************* QUESTION 3. Is there any rule to determine whether a language is acceptable, decidable by a TM, any methods? ******************************************* No. You have to come up with a TM or you have to show that the problem can be reduced to another problem that is known to be acceptable or decidable. ************************* QUESTION 4. If a function does not depend on the argument, it is decidable? *********************************** Yes. ************************* QUESTION 5. Could you help us to summaries the example we have gone through in lectures, but not on the sildes? **************************** All examples are on the slides or will be discussed during the discussion of the homeworks. In addition, you should play around with these examples and maybe modify them a bit and ask the same questions (time/space complexity, etc). ************************* QUESTION Having gone through the notes very many times, I would like to ask this w.r.t. both parts of the module: How do I study beyond the scope of the notes? The references, I am sure, are too detailed and mathematical for me to follow so how can I reinforce my knowledge and ensure I do well in the exam? I fear that roughly 200 slides are somewhat too concise to stimulate my thinking process and provide sufficient practice. ********************************* You are right that the references are too detailed and there is the danger that you can "overdo" your preparations It is really enough to go carefully through the examples on the slides and the ones we have done on the blackboard. And, of course, the additional homeworks that we discussed during one week (one is still to come) ***************************** QUESTION Also, am I right concluding that the only exam which is similar to this year's exam is last year's exam? ************************ Yes, and it makes sense to try these questions as well. As you can see from last years exam, it is really not difficult. ***************************** QUESTION How do we define a NDTM which can decide integer linear programming Ax > b, given A and B, look for x and what is the complexity of it? I think it is NP. Is that the same as satisfiability problem? ****************************** This is a good question!! What about the following. (1) We guess an x ( a vector). (2) Then we carry out the matrix multiplication Ax and (3) then we check whether Ax >b. The complexity of (2) is certainly polynomial, and then check in (3) is even linear. So the problem is in NP. But is that right? Just think about it: we'll discuss it on Monday, May 12th. ***************************** QUESTION %Ok, here are my answers to question 2 from last years exam % %"Given a language L that is accepted by a Turing Machine M (NDTM) %which is space bounded 3^n. Answer the following questions and %explain your answers. % %a) What can you say about the termination of M? Does it always %terminate, or only on particular inputs?" % %ANSWER: Assuming that the NDTM given is a one tape machine, using %Theorem 2.4(Reduction of Tapes) there is an equivalent space %bounded off-line NTM. So L is a member of NSPACE (3 ^ n) using %Theorem 2.6 this implies L is a member of DSPACE (3 ^ 2n) which %implies it is a member of DSPACE (3 ^ n) using Theorem 2.5 this %implies L is a member of DTIME (c ^ 3 ^ n) This is all ok, but I %did not really ask all that. I was just asking about termination. % %This means M can only run for a finite amount of time before %looping. Therefore if another tape can be used to count the number %of steps taken, it can force the machine to terminate after c ^ 3 %^ n steps. Otherwise, the machine may loop indefinately. This is %all ok. But what is the answer to the question? The answer is: the machine might not always terminate. It might do so on some inputs. And as you correctly described, one might modify the machine slightly to make it terminate on all inputs (but that is question b). %QUESTION "b) Can L be accepted by a DTM?" % %ANSWER: Yes because there is an equivalent DTM to every NDTM. Yes, perfect. %QUESTION "c) Can L also be accepted by a DTM that always %terminates?" % %ANSWER: Again, this depends on whether there is another tape %which can be used to count the number of steps taken. If so, M %can be forced to terminate after c ^ 3 ^ n steps The additional assumption that there is another tape is in fact not an additional asumption: the notion of a DTM has this for free. One can always simulate another tape by adding new states (on the slides). So the answer is simply a big fat yes. %QUESTION "d) Is the complement of L decidable?" % %ANSWER: Yes, just run to the maximum number of steps and return %true if answer has not been found. Perfect. % %NOTE: I was not really sure about this one. The notes state that %complexity classes defined on DTMs are closed under %complementation - but does this include DTIME (c ^ 3 ^ n)? Of course, the function inside does not matter, only that it is a deterministic one. This is because then one can do the swapping. %QUESTION "e) Suppose that there is no polynomial space bounded %NDTM which accepts L. Show that L is not a member of NP." % %ANSWER: L is not a member of NSPACE Using theorem 2.6 (PSPACE = %NSPACE) L is not a member of PSPACE (either) this implies L is not %a member of NP Right. % %but i couldn't find the Theorem which states it explicitly. But this is trivial: NP is a subset of PSPACE (because if it is time bounded by a polynomial, then it is also space bounded by a polynomial.. %I also have a question concerning NDTMs. I've read many times %that the algorithm for finding whether a number is prime or not is %in NP. I've created a DTM to check if a number is a factor of %another, but i fail to see how this can be extended to the prime %problem with a NDTM. Given that a NDTM has only a finite number %of possible moves it can make for each ID it is in, how can it %guess the arbitrary number of possible factors that a number can %have? Here is a description of the NDTM. 1 step: Guess any number less than the input. 2. step: Check whether this number is a factor of the input. If yes: Print not a prime. If no: Print No. Note that according to our definition of acceptance of a NDTM this is perfectly correct: If it says yes, then the number is not a prime (because a factor has been found). However if it says no, you can not conclude anything: it might have just chosen not the right factor. But if the input is not a prime, then there is a nondeterministic choice (guessing the right factor) that gives a yes. This also illustrates quite clearly why you can not swap answers for a NDTM. Here are my answers for this question: \begin{enumerate} \item \textbf{(6 points)} It needs not terminate on all inputs: a TM using only a finite amount of space might well go into a loop. Only on those inputs $w$ that belong to the language is $\mathscr{M}$ guaranteed to stop. \item \textbf{(2 points)} Yes, each NDTM can be simulated by a DTM: we just have to take into account all possible nondeterministic choices. \item \textbf{(4 points)} Yes. Because of 2.~we can assume $\mathcal{L}$ is accepted by a space bounded DTM. But each language accepted by a space bounded DTM is also accepted by a time bounded DTM. And time bounded DTM's always terminate. \item \textbf{(4 points)} Yes. Because of 3.~, $\mathcal{L}$ is not only accepted by a DTM, but also decided (since the DTM always terminates). Therefore the same machine can be easily modified to decide the complement of $\mathcal{L}$: just swap the answers. \item \textbf{(4 points)} If the language were in \NP, then it would be polynomially time bounded. This would imply that it is also polynomially space bounded, which it is not. \end{enumerate} ***************************** QUESTION %My question about the prime problem was really concerned with how %one comes up with the guess. When the machine reaches a variable %and makes two possible moves, is it as if there were now two %different machines working on two seperate tapes? (A bit like %using the old fork instruction in c) You can implement it as follows. You let the machine print 1's on a separate tape nad, nondeterministically, terminate it after some time. Something like: machine is in state q1, print 1, go right and go into state q1 **or** into state q2. This ensures that a number (any number) of 1's is printed until, suddenly, the machine goes into state q2. In this state, it is taking the number just constructed and checking whether it is a factor of the input. So there are not 2 different machines. The machine decides which way to go. Next time, it might take another step. ***************************** QUESTION %Question 1: Consider the alphabet S = {a, b} and the language % %L odd = {w is a member of S* : e /= w, w consists of an odd number %of symbols} % %a) Define a DTM that accepts this language. % %Answer: # a b q0 q1 - % q2 - % %q0 is the start state. q1 is the success final state. q2 is the %fail final state. Perfect. %Question: b) Is L odd also decidable? Give a brief argument. % %Answer: Yes. "L odd" is linear. It stops for every input  w. if w %is a member of Lodd it ends in state q2. Otherwise, it finishes in %state q1. "It" meaning the DTM that you just defined. You have to distinguish the machine from the language. %Question: c) In which time complexity class is L odd, i.e. give a %f:N->N (f should be as small as possible) such that "L odd" is a %member of DSPACE(f(n)) % %Answer: "L odd" scans each element in the input once. Therefore, %Lodd is a member of DTIME(n + 1). Perfect. %Question d) In which space complexity class is L odd, i.e. give a %f:N->N (f should be as small as possible) such that "L odd" is a %member of DSPACE (f(n)) % %Answer: "L odd" does not need to write to any of the storage %tapes. Therefore, "L odd" is a member of DSPACE(1). Perfect. %Question e) What are the corresponding results for the following %language "L even" = {w is a member of S* : e = w or w consists of %an even number of symbols}? % %Answer: The results are both the same as "L even" is the %complement to L odd. Perfect. %And here are my answers to question 3. % %Question Are the following statements true, false or unknown to %science? Explain your answers briefly % %i) The complement of a language in DSPACE(log ^ 3 (n)) is also in %DSPACE(log ^ 3 (n)). % %Answer: True - If a language belongs to a complexity class defined %on a deterministic machine, so does its complement. Perfect. %Question: ii) There is no NP-complete problem whose complement is %also NP-complete. % %Answer: This is unknown to science. Say a language L and its %complement were NP-complete. L would be poly-time reducible to its %complement. As L is complete, every member of NP would be %poly-time reducible to its complement. This would make NP = co-NP %which is unknown to science. Yes. %Question: iii) Any NP-complete problem is also P-complete % %Answer: If an NP-complete problem was P-complete it would be a %member of P which would mean NP would be a subset of P. This %implies that P = NP. This is unknown to science Yes. %Question: iv) Any DSPACE (log n)-complete problem is also PSPACE %complete. % %Answer: False. This would mean that any PSPACE problem would be %poly-time reducible to any DSPACE (log n) problem. This conflicts %with Theorem 2.7 which shows that DSPACE(log n) is a strict sub %set of PSPACE. Perfect. %Finally, i was looking through the past homeworks and i came %accross the following question. "Homework 3: Question 3: What is %the relationship, if any, between these two complexity classes? %DTIME (2 ^ n) and DTIME (3 ^ n)." % %Through reading my notes, i see that a hint was given in a lecture %to use Theorem 2.7, i.e. the rule that if T1(n) lg T1(n) / T2(n) %tends to 0 as n tends to infinity, then DTIME (T1(n)) is a strict %subset to DTIME (T2(n)). However, this is not the case in either %direction. You get something like (2/3) ^ n * n, which would tend %to infinity as n did. Does this mean that there is no relation %between the two classes? No, the fact that this limit does not exist in either direction, does not mean that there is no relation: the theoremn says "if this holds, then ther is the subset relation". But, in fact, the limit does exist and is 0. I remember that I was using the de l'Hopital rule for establishing the limit. I was asking the french fellow whether he knows this rule (de l'Hopital was a french mathematician some centuries ago). The rule says: if you have a quotient where both parts tend to infinity, then the limit, if t exists, is the same when you are taking the derivatives for both parts. That often helps. Here we get: we write 2^n n / 3^n as n/ (3/2)^n and apply de l'Hopital. We get 1 / n (3/2)^(n-1) which clearly goes to 0.