Hi all,
I know there has been a long pause on my blog. Well, it was a transition period for me from IRL to IITK. Yes, I have joined its CSE department as a PhD student. Anyways, I know the title is somewhat misleading as many would think this post has something to do with einstein's theory of relativity and the four dimensional world. You are grossly mistaken if you think so.
Actually, as part of my coursework here I am attending a course by Prof Manindra Aggarwal. Well, it is a big mistake on my side that I have not registered for this course. Even the bigger mistake is that I have registered for a course named "Computational Number Theory and Algebra" by Prof Piyush Kurur. The content itself may be interesting but the way that guy teaches the course, makes it difficult. The worst part is that all the exams of this course are "take home" exams.
Anyways, let's get back to the point. It is indeed an honour to sit in Prof Manindra's class and see him deliver some of the toughest content of the course with a flair. All the people with computer science background are aware of the P not equals NP conjecture. This decade old conjecture has still remain unbeaten. In other words, this conjecture states that the set of problems that can be solved by a deterministic turing machine in polynomial time and the set of problems that can be solved by a non-deterministic turing machine in polynomial time are equal.
There is another notion called Space Complexity in computer science. Space complexity is a measure of the space required to solve any problem by an algorithm. One wonders, whether there is any difference between the set of problems which can be solved by a deterministic turing machine in polynomial space , and the set of problems which can be solved by a non-deterministic turing machine in polynomial space. It actually turns out that non-determinism does not give any more power over deterministic mechanism when space is the criterion. Due to Savitch's theorem it is proven that PSPACE equals NPSPACE.
One may wonder why the similar version in time complexity is yet unbeaten? Non-determinism gives the power to explore exponentially many threads of computation simultaneously. If a deterministic turing machine tries to mimic the behaviour of a non-deterministic one, it has to explore all the paths one by one. It costs time to go through all the paths one by one. One has to add up all the time that has been spend. But does one really have to add up the space as well??? I felt really stupid when I come to know that the reason why power of deterministic and non-deterministic turing machine comes out to be same, is that space can be reused!!!!
As a wild thought, may be if a deterministic turing machine can go back in time to explore the alternate future, thus, reusing the time we may as well have P = NP :D.
Showing posts with label theorems. Show all posts
Showing posts with label theorems. Show all posts
Sunday, August 19, 2007
Friday, May 11, 2007
Necklace Theorem
Hi all,
As mentioned in my last post, after lunch talks can be very fruitful at times. Describing a yet another fruitful chat with my friend Sambuddha Roy.
The other day he gave me an interesting problem to think about, which is formerly known as, as he told me, necklace theorem. Two thieves have stolen queen's very precious necklace. There are three kinds of gems in the necklace called R, G and B. All are even. The problem is to divide the necklace in such a way that both the thieves get equal amount of gems of each kind. The necklace can have any interleaving of the gems. ( e.g. RRGBGGRBBBG..... ) Prove that it is always sufficient to divide the necklace in equal share by at most 3 cuts.
The proof makes use of Ham Sandwich Theorem. For brevity, I will quote it as HST now on. HST for 2-dimension says that given any two point sets in a plane, there always exist a line which will cut both these point sets simultaneously into half. To say it more formally, call the point sets R and B. Then one side of line will contain at most |R|/2 points and at most |B|/2 points. The same constraints will be followed on the other side too.
If there is only 1 point set R. For a given direction we can always have a line which will divide R in two. The proof is based on intermediate value theorem. It says that for a continuous function if f(x1) = 0 and f(x2)=1 then there exist a z \in (x1,x2) such that f(z) = 1/2.
Now that we have two point sets. What we can do is we get a line for point set R. Now we evaluate how this line L behaves with respect to B. Let us define diff(L) = number of blue gems on the left of L - number of blue gems on the right of L. For initial line L, let the value of diff(L) be b. What we can do is rotate this line a bit. We know that for any given direction, we have a corresponding line L which will divide R equally. We will again evaluate wrt B. We keep on doing this until we have rotated the line for 180 degree. At this point value of diff(L) would be -b. From intermediate value theorem, we can state that there will be a line where diff(L) will be 0.
How about, Ham Sandwich theorem in 3-dimension?? Well, my friend has given me the proof as an exercise. The statement is that given 3 point sets R, G, B in R^3 ( or 3-dim space ) there always exist a plane which will divide all 3 point sets simultaneously into equal portion.
Now, we need to reduce Necklace Theorem to HST in 3D. Starting from left to right, assign every gem an index i. Plot a parametric curve ( t, t^2, t^3 ) using these indices. HST assures us that we will have a plane ax+by+cz+d=0 which will divide R, G, B equally. This plane will divide the parametric curve at , at most 3 points as at + bt^2 + ct^3 + d = 0 will have at most 3 roots. Now, it is easy to map these 3 intersection points on the curve to 3 cuts on the necklace.
Phew!!! It never occurred to me that this proof will use such weird things. Induction based method was too tempting for me to let me think in some different direction. But the story is not over yet. The proof given above is not constructive. So if we were to find an algorithm to find these 3 cuts we might have to explore all possibilities taking O(n^3) time. So another exercise would be to try to find more efficient algorithm to find these cuts.
The generalization of HST is that given k point sets in R^k there would be always be a hyperplane which would cut all these k point sets simultaneously into equal portion. Yet another generalization one can think of is that, what if there are more thieves??? Given q number of thieves and k kind of gems, what would be the upper bound on the number of cuts required?? The answer is due to dold's theorem ( Neither sambuddha nor I have read the proof ). It say that for such situation at most k(q-1) cuts would be necessary.
What if there are 3-point sets in two dimension?? Definitely a line would not suffice. An exercise would be to prove that two rays originating from an apex would be sufficient. Give an algorithm for finding them out.
Two more puzzles are :
1) Given a point set of size n in 2D, prove that there would exist a pair of orthogonal lines which would divide the point set in such a way that in each quadrant number of points are at most n/4.
2) Given a point set of size n in 2D, prove that there would exist 3 concurrent lines which would divide the point set in such a way that in each segment the number of points are at most n/6.
That's enough to tease our brain for a while :D.
As mentioned in my last post, after lunch talks can be very fruitful at times. Describing a yet another fruitful chat with my friend Sambuddha Roy.
The other day he gave me an interesting problem to think about, which is formerly known as, as he told me, necklace theorem. Two thieves have stolen queen's very precious necklace. There are three kinds of gems in the necklace called R, G and B. All are even. The problem is to divide the necklace in such a way that both the thieves get equal amount of gems of each kind. The necklace can have any interleaving of the gems. ( e.g. RRGBGGRBBBG..... ) Prove that it is always sufficient to divide the necklace in equal share by at most 3 cuts.
The proof makes use of Ham Sandwich Theorem. For brevity, I will quote it as HST now on. HST for 2-dimension says that given any two point sets in a plane, there always exist a line which will cut both these point sets simultaneously into half. To say it more formally, call the point sets R and B. Then one side of line will contain at most |R|/2 points and at most |B|/2 points. The same constraints will be followed on the other side too.
If there is only 1 point set R. For a given direction we can always have a line which will divide R in two. The proof is based on intermediate value theorem. It says that for a continuous function if f(x1) = 0 and f(x2)=1 then there exist a z \in (x1,x2) such that f(z) = 1/2.
Now that we have two point sets. What we can do is we get a line for point set R. Now we evaluate how this line L behaves with respect to B. Let us define diff(L) = number of blue gems on the left of L - number of blue gems on the right of L. For initial line L, let the value of diff(L) be b. What we can do is rotate this line a bit. We know that for any given direction, we have a corresponding line L which will divide R equally. We will again evaluate wrt B. We keep on doing this until we have rotated the line for 180 degree. At this point value of diff(L) would be -b. From intermediate value theorem, we can state that there will be a line where diff(L) will be 0.
How about, Ham Sandwich theorem in 3-dimension?? Well, my friend has given me the proof as an exercise. The statement is that given 3 point sets R, G, B in R^3 ( or 3-dim space ) there always exist a plane which will divide all 3 point sets simultaneously into equal portion.
Now, we need to reduce Necklace Theorem to HST in 3D. Starting from left to right, assign every gem an index i. Plot a parametric curve ( t, t^2, t^3 ) using these indices. HST assures us that we will have a plane ax+by+cz+d=0 which will divide R, G, B equally. This plane will divide the parametric curve at , at most 3 points as at + bt^2 + ct^3 + d = 0 will have at most 3 roots. Now, it is easy to map these 3 intersection points on the curve to 3 cuts on the necklace.
Phew!!! It never occurred to me that this proof will use such weird things. Induction based method was too tempting for me to let me think in some different direction. But the story is not over yet. The proof given above is not constructive. So if we were to find an algorithm to find these 3 cuts we might have to explore all possibilities taking O(n^3) time. So another exercise would be to try to find more efficient algorithm to find these cuts.
The generalization of HST is that given k point sets in R^k there would be always be a hyperplane which would cut all these k point sets simultaneously into equal portion. Yet another generalization one can think of is that, what if there are more thieves??? Given q number of thieves and k kind of gems, what would be the upper bound on the number of cuts required?? The answer is due to dold's theorem ( Neither sambuddha nor I have read the proof ). It say that for such situation at most k(q-1) cuts would be necessary.
What if there are 3-point sets in two dimension?? Definitely a line would not suffice. An exercise would be to prove that two rays originating from an apex would be sufficient. Give an algorithm for finding them out.
Two more puzzles are :
1) Given a point set of size n in 2D, prove that there would exist a pair of orthogonal lines which would divide the point set in such a way that in each quadrant number of points are at most n/4.
2) Given a point set of size n in 2D, prove that there would exist 3 concurrent lines which would divide the point set in such a way that in each segment the number of points are at most n/6.
That's enough to tease our brain for a while :D.
Tuesday, November 14, 2006
Godel's incompleteness theorem
Yesterday I was opportune to watch Dr Raja elucidate the proof of Godel 's
incompleteness theorem .
I still do not know much details of the theorem so I writing it down here in an informal manner.
Basically, what is states is " A statements can be constructed in an axiomatic system which is true but can not be proved or disproved using the axioms of the given axiomatic system ". Or the other statement goes like "No consistent axiomatic system can be complete".
The example that Dr Raja explained goes something like this.
Let there be an alphabet sigma = { (, ), P , N , ~ }
Let there be expression X \in sigma^*
Let us define N(X) to be X(X) called the norm of X
There are four kind of sentences in this language
P(X) - P(X) is true iff X is printable
~P(X) - ~P(X) is true iff X is not printable
PN(X) - PN(X) is true iff N(X) is printable
~PN(X) - ~PN(X) is true iff N(X) is not printable
Let us also have a machine which prints only true sentences. ( in other words only true sentences are printable by the machine )
So now, if X is printable, so is P(X)
Given that a machine prints X then P(X) is true but will the machine print it??
or in other words, is the machine able to print all the true sentences???
The answer to this question is NO
Can you form a sentence which is true in the system discribed above but still won't be printed by the machine?
Hint : Because this is a self referential system, one can think of a sentence which tries to make statement about its own printability.
If you can not think of such a sentence...dont worry as I also was not able think of that then.
The answer is ~PN ( ~PN ) the sentence is true and yet it is not printable. the negation of the sentece is PN ( ~PN ) is false hence won't be printed by the machine.
For axiomatic system one can try to substitute the concept of printability to provability and can derive similar example as well as conclusion.
I have written down whatever I have understood from the talk and whatever I could remember. The information may not be precise or some incosistency may have been introduced because of the long path of information transfer :D
I wish I get such opportunities frequently :-) I am looking forward to IRL workshop for that.
incompleteness theorem .
I still do not know much details of the theorem so I writing it down here in an informal manner.
Basically, what is states is " A statements can be constructed in an axiomatic system which is true but can not be proved or disproved using the axioms of the given axiomatic system ". Or the other statement goes like "No consistent axiomatic system can be complete".
The example that Dr Raja explained goes something like this.
Let there be an alphabet sigma = { (, ), P , N , ~ }
Let there be expression X \in sigma^*
Let us define N(X) to be X(X) called the norm of X
There are four kind of sentences in this language
P(X) - P(X) is true iff X is printable
~P(X) - ~P(X) is true iff X is not printable
PN(X) - PN(X) is true iff N(X) is printable
~PN(X) - ~PN(X) is true iff N(X) is not printable
Let us also have a machine which prints only true sentences. ( in other words only true sentences are printable by the machine )
So now, if X is printable, so is P(X)
Given that a machine prints X then P(X) is true but will the machine print it??
or in other words, is the machine able to print all the true sentences???
The answer to this question is NO
Can you form a sentence which is true in the system discribed above but still won't be printed by the machine?
Hint : Because this is a self referential system, one can think of a sentence which tries to make statement about its own printability.
If you can not think of such a sentence...dont worry as I also was not able think of that then.
The answer is ~PN ( ~PN ) the sentence is true and yet it is not printable. the negation of the sentece is PN ( ~PN ) is false hence won't be printed by the machine.
For axiomatic system one can try to substitute the concept of printability to provability and can derive similar example as well as conclusion.
I have written down whatever I have understood from the talk and whatever I could remember. The information may not be precise or some incosistency may have been introduced because of the long path of information transfer :D
I wish I get such opportunities frequently :-) I am looking forward to IRL workshop for that.
Subscribe to:
Posts (Atom)