Are we asking for too much?

I recently realized, while reading Garey and Johnson’s famous book on NP-completeness that a very large number of naturally occurring problems are NP-hard (which is just a more mathematical way of saying really really hard). I mean, I had heard this during my undergrad years from different professors, but I never actually realized how bad the situation was. Now, after reading the long list of NP-hard problems given at the end of the book, it seems that you come up with any random problem and the chance that it turns out to be NP-hard is very high.

Just to give an example, suppose you have been given many tasks with their own respective deadlines. You have k different processors on which you can schedule the tasks, or in other words, at most k tasks can be carried out simultaneously. And finally, each task has certain dependencies, that means, each task can be started only if certain number (0 or more) of other tasks have been completed already. Then deciding whether it’s possible to finish all tasks before their respective deadlines is NP-hard. And this is just an example. There are many other similar very simple and naturally occurring problems that turn out to be NP-hard.

This makes me wonder – is it really asking for too much to have a general algorithm that solves a given problem efficiently for all of its instances?

Sad atheism

When people realize that I am an atheist, they have different responses. For example -

• “Ok, but that’s your own opinion and hence, not necessarily the truth.”
• “Oh, really? Why so?”
• “Nice! I am an atheist too! High five!”

The weirdest response I have ever heard though, is this -

• “Oh why? Did you go through some kind of traumatic experience when you were a kid?”

I was confused when I first heard it. Why the hell would a childhood traumatic experience convince me to turn into a non-believer? But then I thought long and hard about it and figured out what the connection was.

Have you seen one of those movies where the protagonist gets utterly screwed in his childhood (like, gets kidnapped while his parents are murdered, house gets stolen by the mafia, starts a shoe-polish business at the railway station but people don’t give him money and sometimes kick him in the nuts as a bonus etc etc.), when one day, out of frustration, he goes to the temple (or church, whatever) and has a long and emotional monologue with God whose one sentence  summary is – “Alright, you screw up with me, I am going to stop believing in you.”? This is what the connection was. The person thought I was like that protagonist.

Oh well, as the great science fiction writer Larry Niven once said – “There is no cause so right that one cannot find a fool following it.”

Anyway, I think it would be really really sad if someone was an atheist for this reason. Seriously.

Optimum number of credit cards in one slot of your wallet…

…is 2.

Because if you keep more, then it gets difficult to take out the one in the middle and if you keep less, then you’re not utilizing space efficiently.

Search phrases that lead to this blog

Whenever someone searches for something and reaches my blog as a result, wordpress shows that search phrase in my dashboard. But it shows only some five or six at a time and then replaces them by new ones. So I just thought of documenting them. Check out the side bar, under the heading “Search phrases that lead to this blog”. I plan to update it whenever my dashboard shows something new.

Are you sure?

Let’s say you work in a hospital. One random day, I come to your office and ask, “Is it going to rain today?” You look outside and see that it’s not particularly cloudy but it’s not one of those bright sunny days either. You have seen days like this pass without a single drop of rain and you have seen days that start like this and end in a flood. So you say, “I am not sure.”

Since I like asking questions, I don’t stop here and instead, I say, “What’s the probability that it will rain today?” You think for a while. You try to remember the number of days which started like this in your life and the fraction that ended up in rain. But to your disappointment, you don’t have that sharp a memory. You try to estimate this fraction, but very soon realize that you have absolutely no clue what it is. So you say, “I am not sure.”

Now let’s pause here and ponder for a while. Whenever someone says ‘I am not sure’ for any question, it is only reasonable to ask them to assign a probability distribution to the set of possible answers to the question. For example, if it is a yes/no question, then the natural thing to ask in reply is, “So what’s the probability that the answer is yes and what’s the probability that it’s no?” If the set of possible answers is, say {1, 2, 3}, that is, the set comprising the numbers 1, 2 and 3, then you will want to ask, “What’s the probability that the answer is 1, what’s the probability that it’s 2 and what’s the probability that it’s 3?” The set of answers may not be countable, that is, it may occupy a continuum. But you can still ask to assign a probability distribution to the set of answers. If you don’t understand how, then this post will not make any sense to you.

Anyway, the point is, when I ask you to assign a probability to the event that it rains today and you say you are not sure, I can ask you to assign a probability distribution to the different values of probability with which it might rain today. This means that I can ask you for the probability that the probability that it rains today lies in a small interval around x, where x is a real number between 0 and 1. And if you claim you are still not sure, you know what I can ask next. Let me still state it, just for the kicks. The question I will ask next is this – “What is the probability that the probability that the probability that it rains today lies in a small interval around x, where x is a real number between 0 and 1?”

I am going to state something really interesting in this paragraph. But before that, I will need to number these questions so that I am able to state the interesting thing in a precise way. So let’s say the question “Is it going to rain today?” was my zeroth question. The question “What’s the probability that it rains today?” was the first question and so on. So here comes the interesting thing. If you choose to answer my nth question, instead of just saying that you are not sure, then from the values that you give me, I can calculate your answer to the (n-1)th question (with a simple integration), and from there, I can calculate the answer to the (n-2)th question and so on till the first (not the zeroth) question. Or in other words, if you are sure about the nth question in the series for any value of n, then you must be sure about the first question as well, or else you don’t understand probability. Or, stated in the contrapositive, if you are not sure about the first question, then you cannot be sure about any of the questions in the series. Or, finally, to summarize everything, you either know the answer to all questions in the series (the set of questions from the first question to the last question) or you don’t know the answer to any one of them.

Some time ago, I was thinking about these things and was trying to figure out what was wrong when I realized something that made it all clear. What I realized was as follows. When I ask you what’s the probability that a certain event will happen, I am not asking you to give me some magic number so that if I perform a certain experiment in similar conditions a hundred times, then the event in question will happen that many number of times. What I am actually asking you is to give me an estimate of your own uncertainty about the event, based only on the information that you currently have. So if you have absolutely no idea if it will rain today or not, you should assign a probability of half to the event that it rains. Other people might assign different values to the probability. But it won’t mean that any one of them is wrong. The probability that one assigns to a certain event’s occurrence shows his own uncertainty about it.

This is why Bayes’ Theorem makes sense. It gives you a precise way to update your own uncertainty about something based on the knowledge you receive and the evidence you assimilate.

So, to sum it up, the problem I tried to explain in the post was that you either know the answer to an infinite number of questions or you don’t know the answer to any one of them. The way it is resolved is that you actually know the answer to all the questions, because the reason the questions sounded unanswerable earlier was that you had not understood them correctly.

This is good understanding for the start. I plan to read E.T. Jaynes’ Probability Theory: The Logic of Science some time soon. I hope I will be wiser after that.

Portable handrest

Hands are useful. I have full respect for them. I don’t know what I would do without them.

But there is a problem.

I don’t know what to do with them when I am not using them. They are not like the other body parts that mind their own business when not in use. Take ears for example. They just sit quietly on the sides of your head all the time, even when you don’t need them. But hands hang from your shoulders in an awkward way and make you look funny. In fact, thanks to gravity for at least pulling them down, or else, they would probably just start floating in the air.

People have tried coming up with solutions. For example -

And some rather extreme ones too, such as -

However, one thing that’s pretty evident from all this is the following – they are all clueless.

So I suggest making a simple device that will solve all problems. It’s a device that I like to call portable hand rest. The way I imagine it is that it would look like something that can be worn around your waste with two padded things coming out of it on which you can keep your hands. The padded things would be foldable, so that you can fold them back when you don’t need them.

Eating yourself

Recently I was thinking of interesting ways of completing the following sentence – “I am so hungry that I can eat _____.”

One interesting way I could think of was this – I am so hungry that I can eat myself – which then led me into thinking if such a situation can actually occur. Or to be more precise, does there exist a situation where eating yourself will lead to a larger chance of your survival than just staying hungry? This can be answered trivially. The answer is no, because eating yourself will always lead to your death (Proof – Let’s say it doesn’t and so you successfully finish eating yourself. Since in the end you have been eaten, you must be dead, which is a contradiction), but staying hungry may not. But then what about the following variation of the above question – does there exist a situation where you will have a larger chance of surviving if you eat a part of your own body than if you stay hungry?

This, now looks more like a question for a person with a good understanding of the human anatomy. However, I being someone who has absolutely no understanding of the human anatomy, conjecture that the answer is ‘yes’. The reason is as follows. Not all parts of the human body are crucial to living. Some parts, such as the appendix, are in fact so useless that they can be removed from your body and your body will not notice. However, these parts still contain (I assume) stuff that can be digested by our digestive system to produce some energy. So now consider the extreme case of food deprivation, that is, a situation where you must eat something or else you will die with almost 100% probability. This can happen if you are so starved that your body doesn’t have enough energy to pump your heart. In this case, if you eat your appendix (or some other not very essential body part), you should survive for at least some more time.

However, from a completely different point of view, if the above is true, there is a major bug in the design of the body. It’s rather silly for your body to keep energy shelved into something as useless as the appendix when something as important as the heart needs it, especially because just removing the appendix from its original place and putting it into the digestive tract does the trick. When there is energy present in the body itself, albeit in a rather inaccessible corner, there should be some mechanism to use it. Or may be, there exists such a mechanism. That’s why I said this is a question for someone with a good understanding of the human anatomy.

I will stick with a ‘yes’ though.

Socks

It’s useful to have all of your socks of the same color, because then you don’t have to waste time finding the “other” piece of the pair. Any two pieces make a pair.

Shitting in the middle of an auditorium

Washrooms look like washrooms. You don’t have to look at the sign on the door to say that you are standing in a washroom. They look shiny and bland. They have tiles and generally, very plain colors. They don’t have stuff lying around randomly. And so on.

I will like to change this.

I will like to have a washroom that does not look like a washroom at all, and in fact looks like something that’s the exact opposite of a washroom. For example, a classroom. Or a meeting room. Or a museum. Or a laboratory. There are many options.

So for example, imagine waking up every morning and entering a room that has an expensive carpet and a huge wooden round table in the center with very expensive chairs around it and white boards hung on the wall and a projector kept facing one of the walls and at the center of the huge round table, there is kept, very conspicuously, a western commode.

Alternately, imagine a huge auditorium with a seating capacity of five thousand people and a western commode kept on the stage where you can go and shit.

I think it will be fun if your toilets look like any of the above. I can’t imagine how a person can be sad for a long time if he has such a toilet. He will have to feel funny at least once everyday. I can’t imagine thinking about why you lost your job, or why your girlfriend left you, or why you are overweight while you are shitting in the middle of an auditorium.

Do rich people get bored?

I want to know if the richest man on earth ever gets bored. I often think of the kinds of things one could do just for amusement, provided one had loads of money. For example, if I had an unlimited amount of money, I would never need coffee. I would pay twenty million dollars to Space Adventures and have a visit to the International Space Station instead.