CS605 - Mathematics and Theory of Computer Science
Frequently-Asked Questions
T. Naughton, Department of Computer Science, NUI Maynooth
These are questions I have been asked by email, and that are short enough to be answered by email. Questions requiring more involved answers, or diagrams, etc., will be answered at a subsequent tutorial. The questions in each section are listed in chronological order, so look to the bottom of each section for the latest questions.
Section 1. Reductions, undecidability, and NP-completeness
Q:1.1 In mapping reducibility when you say A <= B it means that A maps/reduces to B and A is at least as difficult as B?
A: No, B is at least as difficult as A.
Q:1.2 A <= B means if we have a solution to B we can use it to solve A?
A: Yes.
Q:1.3 But when we want to prove that HALT is undecidable we say A_TM <= HALT where we know that A_TM is undecidable. In this case we don’t have a solution for either (as in the above case A <= B where we would have a solution for B)?
A: There ARE solutions. Every correctly formatted input is either "true" in the language or "false" not in the language. It's just that we can't compute the solutions using a Turing machine (or C++, Java, etc).
Q:1.4 This reducibility is to show that HALT is undecidable, i.e. if A_TM reduces to HALT then HALT is undecidable. So to show that something is undecidable we put what we know to be undecidable on the left hand side (here it's A_TM) and reduce it to the problem we want to prove to be undecidable. If it reduces (i.e. if you can come up with an f that reduces it) then the unknown is undecidable. Is that correct? Do we always put the known on the LHS?
A: Yes. You always put the known on the LHS when you want to prove that some unknown problem is at least as hard as the known. (You also forgot to say that we know that A_TM is undecidable.)
Q:1.5 To prove something is NP Complete, Eg to prove that the Hitting Set is NP Complete we reduce 3SAT to the Hitting set, 3SAT <= Hitting Set. Is this the same as above, i.e. if 3SAT reduces to Hitting Set then Hitting set is at least as hard as 3SAT, and to prove it's NP Complete you then have to show that it's in NP and show that f is done in polynomial time?
A: Yes (but you forgot to include that we know that 3SAT is NP-complete).
Q:1.6 In Sipser's book, page 277, it says "If one language is polynomial time reducible (say Hitting set) to a language already known to have a polynomial time solution (say 3SAT), we obtain a polynomial time solution to the original language". But in our example we say it the other way around, 3SAT reduces to the Hitting Set. I don't understand why it goes the other way around.
A: Here Sipser is doing the opposite. He's not trying to prove that the unknown is at least as hard as the known, he's proving that the unknown is as easy or easier than the known. That's why they are the other way around in this case. It's just the same for integers. Let's say we prove the relationship a <= 7. This proves that our unknown a is less than or equal to 7. Let's say we prove 3 <= b. This proves our unknown b is greater than or equal than 3.
Q:1.7 Does recursively enumerable mean Turing recogonisable?
A: Yes, they mean the same thing. Some textbook authors use the first phrase to describe those languages, and others (including Sipser) use the second phrase.
Q:1.8 When proving that a problem is undecidable do we always use a high level description of a TM M, and its input is an NFA, DFA etc?
A: Yes, we will always use a high-level (pseudocode) description of a TM. Each word in the undecidable language will most likely be a TM and some particular strings/integers.
Q:1.9 Why would we want to prove that a problem is TR, decidable, undecidable, NP Complete? Whats the reason behind what we're doing? Is it so we know what problems cant be solved etc?
A: When we prove that a problem is undecidable then we prove that it can't be solved completely by computer, and that the problem shouldn't, in general, be tackled with a computer. When we prove a problem is TR and undecidable, we prove that all "yes" answers to that problem can be solved, but any instances of the problem that give rise to a "no" answer can't be solved with a computer (and, of course, there is no way of knowing in advance which instances are which). When we prove that a problem is decidable, we prove that it can be completely solved with a computer. When we prove that a problem is NP-complete we prove (i) that although it can be solved exactly by computer it is a problem for which no known efficient computer solution yet exists (so it should be approximated rather than solved exactly), and (ii) if it can be solved efficiently then that exact computer program can be used to efficiently solve all other NP-complete problems (such as 3SAT, timetabling, travelling-salesperson problem, etc.).
Q:1.10 Do we use F in the high level description of a TM only when we are using a mapping reducability?
A: If your question is do we only use F in mapping reductions rather than in other reductions (such as Sipser's subroutine reductions in the beginning of Chapter 5), then the answer is yes. If your question is do we only use high-level descriptions of TMs in mapping reductions, then the answer is no, we also use them to prove decidability, prove membership of NP, etc.
Q:1.11 Could you go through the theory to solving a problem is NP Complete just to confirm what we did in our reports. i.e. are we showing that it's NP Complete because that shows that it is more than likely not polynomially time solvable? Jan 2005 exam Paper Q2 c
A: Yes, one obvious result would be that the problem is probably unlikely to have a polynomial time solution (our current best guess is that P != NP). Another reason to be interested in what problems are NP-complete or not is that it gives us a better understanding of the concept of computation, and in particular what is the fundamental difference in difficulty between checking the answer to a problem and computing from scratch an answer to a problem. The answer to that specific past exam paper question is: c(i) No implications, because there is no evidence that this exponential algorithm is the most efficient algorithm that solves the problem; c(ii) No implications, because for example addition is in NP and has a polynomial time solution.
Q:1.12 Jan 2005 exam Paper. Q1 d. How can we prove that Halt in undecidable
without using another undecidable problem?
A: This proof assumes that a function halts() to decide Halt exists
bool halts(string < M >, string w) {
// if M halts on w return true
// else return false
}
and then shows the existence of a new function newfn() that calls halts()
void newfn(string X) {
while halts(X, X) {
}
printf("I'm halting now!");
}
and that causes a contradiction because newfn(< newfn >) neither halts nor doesn't halt.
Q:1.13 When proving something is undecidable, when do you know you have to get the complement of it? An example of this would be test 2 you gave us, when we had to prove that LESSj is undecidable in part (a). Why did we have to get the complement of this?
A: When proving some language A is undecidable you will reduce B to A where B is some known undecidable language such as HALT or ATM.
B will always be Turing-recognisable (T-r) as HALT and ATM are.
If A is undecidable then either:
A is T-r and ¬A (the complement of A) is not T-r, or
A is not T-r and ¬A is T-r, or
both A and ¬A are not T-r.
When you reduce B to A you prove that ¬A is not T-r (this is a fact; it is explained in Sipser's book, but you are perfectly fine just accepting it).
So, given some problem A that you have to prove undecidable, you have to figure out which is T-r out of A and ¬A, and reduce B to that one. If both A and ¬A are not T-r then it doesn't matter which you reduce B to.
Some examples (assume you are given that HALT is undecidable):
A = {< P,a >: P is a Java program and a is an integer variable declared in P and a gets the value 0 at least once in the execution of P}. You should reduce HALT to A.
A = {< P,a >: P is a Java program and a is an integer variable declared in P and a never gets the value 0 during the execution of P}. You should reduce HALT to ¬A.
A = {< M,s >: M is a TM and s is a state in M, and M goes into state s at least once during the execution of M}. You should reduce HALT to A.
A = {< M,s >: M is a TM and s is a state in M, and M never goes into state s during the execution of M}. You should reduce HALT to ¬A.
LESSJ = {< J, a, b > : J is a Java program, a, b are integer variables declared in J, and when J is run a is never less than b}. You should reduce HALT to ¬LESSJ.
LESSJ2 = {< J, a, b > : J is a Java program, a, b are integer variables declared in J, and when J is run a is less than b at least once}. You should reduce HALT to LESSJ2.
Q:1.14 If we use the fact that if a language is TR and its complement is TR then it's decidable, can we just use the complement part, i.e. if ¬CHAROUT is TR then CHAROUT is decidable? I want to know because I dont know how to prove that CHAROUT (i..e c++ program that never writes a space to screen) is TR, i.e. how can you check if it never does something.
A: CHAROUT is not decidable, because CHAROUT is not T-r. Even though ¬CHAROUT is T-r, it's not enough to make CHAROUT decidable. As you say yourself, both the language and its complement must be T-r for the language to be decidable. Is that your question?
Q:1.15 Sorry, I meant undecidable. To prove that it's undecidable, could you use 'both the language and its complement must be T-R for the language to be decidable', which is why here we cant prove that CHAROUT is TR? Also, how do you prove that something is not TR?
A: You cannot say that just because you can't think of how to prove that a problem is T-r then it must be not T-r. That approach might help you to get a gut feeling about whether something is T-r or not, but it's not a proof.
CHAROUT is undecidable because CHAROUT is not T-r. ¬CHAROUT (the complement of CHAROUT) happens to be T-r, by the way.
To prove the language CHAROUT is not T-r:
From your email below, I assume that CHAROUT is defined as {< P > : P is a
C++ program that never writes a space to the screen}. Let X be a T-r undecidable language (such as HALT = {< M,w > : M is a TM and M halts on w}). When you reduce X to Y you prove that ¬Y is not T-r. So to prove that CHAROUT is not T-r we reduce HALT to ¬CHAROUT.
Here is the function f in the mapping reduction from HALT to ¬CHAROUT:
F = "On input < M,w > do the following:
1. Construct a C++ program as follows:
P = "void main(void){
Run M on w;
printf(" ");
}"
2. Output < P >."
Now, < M,w > is an element of HALT iff < P > is an element of ¬CHAROUT.
Q:1.16 How to proof a language is Turing-recognizable:Q2(c) in CS605 December 2003
A: We prove VARNEGC++ is T-r by showing the existence of the following Turing machine M that recognises VARNEGC++:
M = "On input < C,v > where C is a C++ program and v is an integer declared in v, do the following:
1. Check if v is initialised to a negative integer. If so, accept.
2. Execute C step by step, checking the value of v at each step. If v is ever assigned a negative value, accept."
Since TM M recognises VARNEGC++, this proves that VARNEGC++ is T-r.
Q:1.17 From the CS370 sample paper for academic year 2003-2004, the online solution for Q2(b) contains the following mapping reduction from ATTM = {< M,w > : M is a TM and w is a word and M accepts w} to INFINITETM = {< M > : M is a TM and L(M) is an infinite language}.
F = "On input < M,w > do the following:
1. Construct the following Mprime given by the following pseudocode:
Mprime = "On input x :
1. If x belongs to {01,11,100}, then accept x.
2. Run M on w.
3. If M accepts w, then accept x."
2. Output < Mprime >."
Can you please explain where x comes from and also why it checks if x belongs to {01,11,100} ?
A: First, two quick answers.
1. The variable x is just the input to Mprime. It could be called anything.
2. The exact contents of the set {01,11,100} is irrelevant. It could be empty, it could be {cat, dog}. The only important characteristic is that it is a finite set.
The shortest explanation that I can give is that Mprime is a machine that accepts a finite set of words if M does not accept w (i.e. if M rejects or runs forever) and that Mprime accepts an infinite set of words if M accepts w.
Now a longer explanation. Mprime is a machine that takes some input word x and either accepts it or not. If M does not accept w (either it does not halt or it rejects w), then there are only three possible input words out of all the possible inputs that will cause Mprime to accept. So we could say that if M does not accept w then Mprime accepts a finite language (3 is a finite language). If however M does accept w then this changes the whole character of Mprime. Now Mprime is a machine that accepts every input x no matter what it looks like (if the input is 01, 11, or 100 Mprime will accept it in line one, and if it is anything else Mprime will accept it in line three.)
So we have a correspondance: if M accepts w then Mprime accepts an infinite language (all words). If M does not accept w then Mprime only accepts a finite language (the language {01,11,100}). That means if we can decide whether Mprime accepts an infinite number of words or not, we'll indirectly have decided if M accepts w or not. Since the latter is undecidable, the first must be undecidable too.
Q:1.18 In CS370 Lab Test 2 (December 2005), Q3, could you explain how you got 4n^2 +4n for the answer in the sample solutions, when working it out we get 3n^2 + 3n?
A: The worst case scenario is where we get a word that's in the language. Let's consider a specific input word (let's pick aaabbbccc, i.e. where n = 3) and go though the pseudocode. The tape head makes n+n+n+1 moves to position itself at the last symbol in the word, and n+n+n steps to get back to what is now the first symbol of the word. So we can see that the first iteration of Steps 1-4 requires n+n+n+1+n+n+n steps. The second iteration of all four steps will require (n-1)+n+(n-1)+1+(n-1)+n+(n-1) steps. The third iteration will require (n-2)+n+(n-2)+1+(n-2)+n+(n-2) steps. Now all that remains is reading n X's and halting when we reach the first blank (Step 5). If you can understand this, you're halfway there.
If we write out the number of steps for an arbitrary n we get the following (where each row is an iteration of steps 1-4 and the last row is step 5):
n +n+n +1+n +n+n
(n-1)+n+(n-1)+1+(n-1)+n+(n-1)
(n-2)+n+(n-2)+1+(n-2)+n+(n-2)
.
.
1 +n+1 +1+1 +n+1
n
Grouping all the terms that decrement at each iteration, this table of rows can be rewritten as:
2n+4n +1
2n+4(n-1)+1
2n+4(n-2)+1
.
.
2n+4(1) +1
n
The number of iterations of Steps 1-4 is n, so this table contains n+1 rows (n iterations of Steps 1-4 and one iteration of Step 5). Summing all of them up (and using Gauss' trick for summing a sequence of numbers from 1 to n) we get
n(2n)+4(n(n+1)/2)+n(1)+n
which can be simplified to
4n^2+4n.
Section 2. Set theory, regular languages, and context-free languages
Q:2.1 Can you explain about pumping length p? In the pumping lemma, s may be divided into three pieces, s=xyz, what's relationship between p and y?
A: There is no particular relationship between p and y, other than maybe saying that |y|<=p, but knowing this relationship is not useful to understanding the pumping lemma. The pumping lemma says that, in a regular language L, each string/word of length greater than or equal to p can be divided into three pieces xyz satisfying the conditions. This length p is used to exclude all short length words in L that would be too short to be divided this way. On it's most simplest level, you could regard the comparison with length p as simply being equivalent to saying "except for the shortest words in L, all words in L can be divided into xyz." A more in-depth understanding of p requires one to appreciate that it represents the number of states in some particular arbitrary FA that recognises language L: Given a regular language L, and a FA to recognise L that has exactly p=25 states (for example), then the pumping lemma states that each word in L of length >=25 can be divided into xyz satisfying the conditions. If we want to use the pumping lemma to prove that a language is not regular, i.e. that no FA can recognise it no matter how many states it has, then we must keep p as a variable and not commit to any particular number of states in our proof.
Q:2.2 In Sipser, on closure under union for regular languages it says that the new machine M created to accept the union of language A1 and language A2, has the set of states Q = Q1 X Q2, i.e. Q1 cross Q2. But in our example in class we said that Q = Q1 U Q2 U q0 (q0 = the start state of the new machine M).
It also says in the book that the start state of M is the pair (q1,q2), i.e. the start states of the machines M1 and M2 that accept A1 and A2 respectively, whereas the example in class created a new start state q0 in M.
Is the book just a different way of doing it using the cartesian product, whereas the class example uses union? Is it ok to understand just one way of doing it?
A: That proof uses deterministic FAs. A few pages later Sipser gives an equivalent, and shorter, proof using nondeterministic FAs. The latter one is the one we did in class. It is OK to understand just one way of proving closure under union.
Q:2.3 Write true/false for the following:
{a,b} is a subset of {a,b,{a,b}}
{a,b} is a subset of P{a,b,{a,b}}
True and false, respectively. The second one is false because every power set is a set of sets; therefore every nonempty subset of a power set must be a set of set(s).
Q:2.4 In the formal definition of an NFA the transition relation is Q X S X Q (where S is the alphabet). But if given a particular NFA you don't have to do all Q X S X Q do you, just the ones that are relevant in the NFA?
A: Yes, that's right. A relation is just a subset of Q X S X Q. It could even be empty (no transitions at all) and that would still satisfy the formal definition of an NFA; a deterministic FA (let's assume it has at least one state and a nonempty alphabet) would not satisfy the formal definition is it had zero transitions.
Q:2.5 The set of regular languages is closed under complement. So swap the accept states and non accept states, but does the transition function stay the same? You still go to the same state on the same symbol as in the original machine?
A: Yes, the transition function stays the same; you still go to the same state on the same symbol.
Q:2.6 To show that the set of regular languages is a proper subset of the set of Context Free languages, can we just state that the set of regular languages is a proper subset of the set of Context Free languages as a theorem and then we just have to find a Context free language that isn't regular?
A: First, a small correction to your question: I assume you meant "...can we just state that the set of regular languages is a subset..." rather than "proper subset" otherwise the question would have been answered. Assuming that's your question, then that would be sufficient for most of the marks. For full marks you could give an informal proof as to why that's true, for example: "A NFA could be regarded as a PDA that ignores its stack, therefore every language recognised by a NFA also has a PDA that recognises it. Since NFAs and FAs are equivalent, this means that every regular language has a PDA to recognise it, and that the set of regular languages is a subset of the set of context-free languages."
Q:2.7 Do we have to know how to use the closure of a class of regular languages under union, intersection and complement to prove that a language is not regular? Sipser, pg 81, just before example 1.75.
A: It is not necessary fr the kind of simple languages you will encounter. However, you would be free to use this technique to prove that a language is nonregular if you wanted, as an alternative to using the pumping lemma. When using this technique, however, be careful about what language you assume in advance is nonregular; you could assume that {a^nb^n : n>=0} or something well-known and simple like that is nonregular, but not something more complicated.