The following are a few selected questions that students asked me by email in the last 2 weeks. The students questions/comments are enclosed in asterisks *****. My answers follow. ************************* QUESTION While revising for the exam I have noticed that your section has a large number of theorems. My question is: to what extent will we be expected to produce proofs of the various theorems? For example, when discussing the various relationships between Time and Space complexity (e.g. section 2.3, theorem 2.5), you give the details of a proof. Will we be expected to reproduce these? Will we be expected to prove properties about new concepts? *************************************** You are not supposed to produce any new proofs. No new concepts. Also, you are not expected to reproduce the proofs of the theorems. I am expecting that you ***understand*** the main theorems. Concerning Theorem 2.5, this really is important, and we did spend more than 2 lectures on it. Again, you are not supposed to reproduce the proof or completetly understand the various countings involved. But you should understand the main idea: - Something that is in DSPACE(f(n)) is not necessarily in DTIME: you can have DTMs using only limited space, but they never halt. So how can you determine whether a given DTM terminates or not (under the assumption that it is DSPACE(f(n) bounded)? Note that without vthis assumption, you can not determine whether it stops or not. The idea is: let's count the ID's!! On a bounded space, there are only finitely many possible. So if we let the given DTM start (on an input), we check the ID's. Two cases could happen: 1. It stops. Then we are lucky. 2. It does not stop. But then it must reach an ID that it already was in. When this happens the first time, we know that the machine will never stop. So we have produced a DTM that is DTIME bounded. This is all you should know. The theorem itself gives you a precise bound, but this is not so important. It is the idea that you should understand. ***************************** QUESTION With regards to tape compression, the notes say that we can replace some number 'r' of adjacent tape cells with a new symbol. We are doing this to prove that DSPACE( S(n) ) = DSPACE( cS(n) ) It then says that r > 2/c in order for this to work.. If we are replacing every 'r' cells on the original machine with a new symbol, then don't we just divide the amount of space required by r? I.e, if we represent 'c' adjacent tape cells with a new symbol, then DSPACE( cS(n) ) = DSPACE( cS(n)/c) = DSPACE(S(n)) So why must r > 2/c? It seems rather odd, that to demonstrate equality between these complexity classes, the larger the value of c, the smaller the required value of r! *************************** I think you got this wrong. The point is, that we make c ***very small***. The theorem is also true for large c's, but that is not the point. We want to speed up, so c must be small; close to 0. The closer to 0, the more we speed up. Using 2/c, the smaller c, the greater is r, which makes perfectly sense, doesn't it? Now how come we consider 2/c, and not just 1/c? Well, if the old machine is moving within the block of r cells everything is ok, and we could do with 1/c. But it is also possible, that the old machine moves from the last cell of the block (the r'th cell) into the first cell of a new block. In that case, the old machine uses two cells, but the new one as well (because it has to go from one block into the other). So on the average, if the old machine uses r cells, the new one uses 2, not just one (because of the overlapping). This exactly is the reason for the 2: it is just doing the right counting. ****************************** Question The time speed up proof says a similar thing, that is, r > 16/c. If we can represent r adjacent cells with a new symbol, and make 8 moves for every r of the original machine, then don't we actually alter the speed by 8/r. Ie. DTIME( T(n) ) = DTIME( 8T(n) / r ) So that, if we choose r = 8c, we get: DTIME( cT(n) ) = DTIME( 8cT(n) / 8c) = DTIME( T(n) ) Again, I am not sure why the notes say that r must be larger than 16/c. Is there something I am missing? ************************************** The same reasoning as explained above applies. Now we have the 16 because 2 times 8 is equal to 16!! The 8 is explained on the slide. Instead of r moves, the new one makes 8 (again for checking the neighbours). ******************************* Question I am unsure as to the exact meaning of the definitions of (D/N)TIME given in chapter 2 of the lecture notes. I thought I understood these terms, but upon closer inspection my knowledge seems a little uncertain. I will try to detail my current understanding, feel free to indicate where my reasoning is unsound. 1) Firstly, the notes say (slide 36) that a T(n) time bounded TM will make at most T(n) moves for every input of length n. (Simple enough) *************************** Yes. This implies of course that the machine halts (unlike space bounded machines). ************************** 2) The language accepted by such a TM is said to be of time complexity T(n). (Also simple enough) 3) DTIME(T(n)) is the class of languages accepted by T(n) time bounded turing machines. Does this mean that every language in DTIME( T(n) ), being accepted by a TM which always halts after at most T(n) moves, is also decided by the same machine? (Hence we could change the above definition to say that DTIME(T(n)) is the class of languages decided by T(n) time bounded machines?) ************************** YES!!! I emphasized this point very often (maybe still not enough). ****************************** 4) NTIME( T(n) ) is the class of languages accepted by T(n) time bounded NDTMs. This is where I get confused.. A language is accepted by an NDTM when there exists a possible sequence of moves leading to an accepting state for each word in the language given as input. What exactly does it mean however, when an NDTM is T(n) time bounded? If we ignore the usual concept of an NDTM 'just doing the right thing' then infact an NDTM makes many simultaneous moves at each point of execution, leading to a set of (maybe terminal) states for each input word that may be reached by the NDTMs possible executions. Quite simply, a language is accepted by the NDTM if an accepting state appears among these possible terminal states for each word in the language given as input. (Some possible executions may lead to no terminal states, looping) ********************************************** Yes, completely right. ******************************* For an NDTM to be T(n) time bounded, does this mean that EVERY possible execution on a particular input must terminate within T(n) steps? ************************************* NO, it is enough that if the input is in the language, than there is one execution path that is T(n) time bounded. But the real point is that you are counting the time it takes for a single execution, not the sum of all of them (that would be an exponential blow-up, because there can be exponential many executions). ************************************* If this is the case, then a language in NTIME( T(n) ) is accepted by an NDTM which cannot possibly make more than T(n) moves, so that a simple extension to the machine in question would allow it to also decide the language in time T(n). (It is probably the exact same machine infact). *************************************** Yes, if you mean "decided by a NDTM". Completely correct. But that does not mean decided by a DTM in the same time bound (see discussion below). ********************************** I doubt this is correct, because it would imply NP=co-NP . If on the other hand, we consider a language to be in NTIME( T(n) ) whenever there is a NDTM which accepts it, and the sequence of moves leading to each accepting state is bounded by T(n), then we reach a different problem.. ************************************* Actually, not each sequence leading to an accepting state is required to be T(n) bounded, only one of them ( ... there exists ...). ************************************* Since we only require the possible execution which leads to acceptance to be T(n) time bounded, does this mean that a decided language only requires a single possible execution to be of maximum T(n) steps? (possibly only when the input word is not in the langauge?) This definition does not appear to work either, since we are now considering the NDTM to just 'do the right thing', is it not possible to construct a new NDTM for any acceptor NDTM which simply counts to T(n) and halts if no accepting state was found? (Thus deciding the language and leading to the aforementioned NP=co-NP problem) *************************************** This is not correct. I think your problem comes from confusing two completely different notions: "decided by a DTM" (this is what we introduced) and "decided by a NDTM" (this is what **you** introduced). Decided by a DTM means: there is DTM such that given an input, the DTM finishes and tells you yes or no. If it does so within a time bound T(n), it is called T(n) bounded. Now suppose a language is accepted by a NDTM in time T(n). How can you decide it (by a DTM) and what is the time bound to do so? Let me stay in your terminology with the execution paths. NDTM: Given an input, you have a lot of choicepoints (guesses). At each such point, you have to choose which way to go. So you are getting a big tree, the paths of which (execution paths) correspond to possible computations. T(n) bounded, means: if given an input of size n, and this input is in the language under consideration, then ***there exists*** an execution path which is T(n) time bounded. DTM: Given an input, you start your deterministic computation. So you are getting exactly one path (not a tree), because you have no choicepoints. T(n) bounded, means: this path is T(n) time bounded. Now let us take a look at what you said above concerning acceptance/decidability (1)). This is true for DTM, but not for NDTM (and this is perhaps the reason for your confusion). If you have only to consider one path, then, at the end, either the input is in or not: if it is not accepted it is not in the language. If it is accepted, then it is in the language. And acceptance in time T(n) also means decidability in T(n). The same reasoning ***is not true*** for NDTM. For suppose you are following one execution path in time T(n). If it is accepted, then it is in the language. So far so good. But if it is not accepted, you can not conclude it is not in the language: you may have just chosen a wrong path. So you have to try another one. This costs you again T(n) time. But you may still have to check another one etc. Only after you checked the whole tree, you can make a statement about the input not being in the language. And the time you need to do this is T(n) times the number of execution paths: this gives you a bound of 2 to the power of T(n). See Theoem 1.2 on slide 31 and Theorem 2.5 on slide 46. I should have better written DTM instead of TM on slide 39!! It seems that you are thinking that the notion is the same whether interpreted as DTM or NDTM. But this is not true. *********************************** QUESTION (Howework 1) ---------------------------- Question 4 - how may ID's are there for an input length n? Am I right to say that if the number of states and the number of tape symbols are infinite, the number of ID's are uncountable? ****************************** It depends. If the number of tape symbols (or states) is countably infinite (I reckon this is what you have in mind), then the number of ID's is still countable. This is because the possible configurations on a part of the tape of length n is countable (just enumerate them in lexicographic ordering ). Multiplying this by the number of states (whether countably infinite or finite) will still result in a countable set (again, you can enumerate them lexicographically). Of course, if the number of tape symbols or states is uncountable right away, then the whole thing is uncountable (even when restricted to an input of length 1). ************************************** QUESTION Slide 30 ---------- Testing for a word mirrored on a central character. You give a DTM and ask to make it a NDTM? How do I do this? ******************************************* Make sure that you understand what the DTM given is doing. It is giving the right result, ***if it is starting on the middle position.*** So you have to do something to ensure that it is on the middle position. Doing this as a DTM is possible, but tedious. The solution is to add just one state (actually the starting state q0) and setting it up in such a way, that the machine is moving to the left (in the beginning) and nondeterministically jumping to state q1 at some time. Think how to do that! Note that in a NDTM we can have more than one entry in the table. ********************************* QUESTION Slide 31 - a language accepted by some NDTM is also accepted by some DTM. One tape on the DTM generates sequences used for choices by the first tape. Does this sequence therefore have to be random? how can you create such a sequence that models non determinism? *************************************** The sequence has to be done the right way. Given a NDTM, there is maximal number, say n0, of choices (the maximal number of triples in one entry of the table of the NDTM). The sequence generated first generates all possible instances of length 1: 1, 2, ... n0 Then all of length 2 (1,1), (1,2), ... (1, n0), (2,1), ... , (n0,n0) and so on. This ensures that the "right" sequence of guesses will be eventually found. Note that we do not simulate the nondeterminism of the NDTM: we just make sure that when the NDTM accepts something, then the associated DTM does as well. ********************************* QUESTION Slide 32 - minimum tapes minimum alphabet does this mean any language can be accepted by an offiline turing machine with a alphabet {#,1}? and similarly with one tape and 3 states? ***************************************** Yes. You can either restrict the alphabet (but then you need many states), or you can restrict the number of states, but then you have to enlarge the alphabet. You can not restrict ***both*** the alphabet and the number of states. ********************************* QUESTION Slide 49 - is there any proof or explanation for theorem 2.6 - NSPACE(S(n)) (= DSPACE(S^2(n))? ********************************************* I decided not to give one. I stated this result only because it is useful later for some other results. No need for you to go into the proof. ********************************* QUESTION Slide 52 - I don't understand how the theorems are applied to NSPACE(n^4) (= NSPACE(n^3) and then on n^3,n^4,n^5 to get a contradiction as shown in the example. ************************************ We want to show that NSPACE(n^3) is a strict subset of NSPACE(n^4). Certainly, by the very definition, NSPACE(n^3) is a subset of NSPACE(n^4). Let's assume, that NSPACE(n^4) is a subset of NSPACE(n^3) and derive a contradiction. Then we have shown our claim. Starting with NSPACE(n^4) subset NSPACE(n^3) and applying Theorem 2.8 for S1(n):= n^3 we get (1) NSPACE(n^12) subset NSPACE(n^9) Applying applying Theorem 2.8 for S1(n):= n^4 we get (2) NSPACE(n^16) subset NSPACE(n^12) and applying Theorem 2.8 for S1(n):= n^5 we get (3) NSPACE(n^20) subset NSPACE(n^15) (1), (2) and (3) taken together give (4) NSPACE(n^20) subset NSPACE(n^9) Then we can use Theorem 2.6 (to combine NSPACE with DSPACE) and get NSPACE(n^9) subset DSPACE(n^18) Since DSPACE(n^18) subset DSPACE(n^20), and DSPACE(f(n)) subset NSPACE(f(n)) we get DSPACE(n^20) subset DSPACE(n^18) which is a contradiction. A bit tricky, but no need to know this for the exam.