Enjoying Life (a little more)
This is a post about a simple trick you can use to enjoy the things you like a little more and/or make them enjoyable to others. But first, let's try a little experiment. Please listen to this piece of classical music. It's only 47 seconds long.
Now write down some measure of how much you enjoyed it on whatever scale you want. Five stars, a number from one to ten, whatever. Ready? Okay, now read the following story.
On the evening of May 7, 1747 in the grounds of the just finished Sansoucci palace of Frederick the Great, King of Prussia, a 62-year old man arrives by carriage. As was the custom in those days, an officer writes his name in a list of visitors which is usually reviewed by the King.
Inside the palace, through the Entrance Hall and to the left, King Frederick is in an exquisitely decorated room, getting his flute ready for the nightly concert while the rest of the musicians tune up. The officer enters the room and gives the King the list of strangers who have arrived to the palace.
With his flute in his hand, Frederick runs down the list and immediately turns to the assembled musicians, exclaiming with a kind of agitation, “Gentlemen, old Bach is come.” He lays his flute aside, and announces to the other musicians and the rest of the people of the court that there will be no concert tonight.
Das Flötenkonzert Friedrich des Großen in Sanssouci by Adolph von Menzel
Johann Sebastian Bach has just arrived for a visit to his son Carl Philip Emanuel Bach, the court’s Capellmeister. The King had been wanting to meet with J.S. Bach, and his wish had just been realized. So without even giving Bach time to change from his traveling clothes to a more formal black chanter's gown, the King summons him to appear before his Highness. Frederick, after listening to Bach’s apology for his appearance, invites him to try his collection of Silbermann fortepianos, which are scattered throughout the palace.
The musicians follow them from room to room, and Bach is invited everywhere to try the fortepianos and play unpremeditated compositions. After going on for some time, Bach asks the King, “Would Your Highness be so kind as to honor me with a subject for a Fuge, so that I can execute it immediately and without any preparation?” The King, desiring to give such a learned musician a challenge, picks up his flute and plays the following tune:
The King's Theme
This is quite a complex melody! One of which Michelle Rasmussen says:
The King’s theme begins with a C minor triad, (“c - e flat – g”), is raised to the next half-note above that, “a flat,” and then takes a dramatic downward leap of a seventh from the "a flat" down to “B,” not included in C minor, but found in C major. This creates musical tension between two pairs of half-step intervals: from the ”B” back to the beginning “C,” and the “g - a flat” interval.
Picking up on these half-steps from the first part, the second part of the Royal theme is a revolutionary ambiguous step-wise descent from the top of the triad, “g” one octave down to "G," comprised of a chromatic descent from "g" to "B", and then, down by major scale steps to “G.” The concluding section hops up through "c" to "f," and ends with a stepwise journey down the C-minor scale from f, through "e flat," to end where it began on "c."
Bach is silent for a couple of seconds, but he accepts the King's challenge. He plays the King's theme three times before proceeding to play a beautiful three-voice Fugue. Please listen to the first minute of it:
The King, impressed by the three-voice Fuge improvised by Bach, and to see how far such art could be carried, requests to hear a Fuge with six voices. Fearing he cannot, without preparation, invent such a complex Fuge based on the King's theme, Bach asks permission of the King to pick his own subject, which the King gently concedes. Bach proceeds then to execute it to the astonishment of all present in the same magnificent and learned manner as he had done that of the King.
After returning home to Leipzig, Bach composes a three-voiced and a six-voiced fugue, ten canons, and a sonata for flute, violin, and piano. All based on the King's theme. This work has become known as the Musikalisches Opfer (Musical Offering), after a phrase from Bach’s dedication to King Frederick[1].
Bach sends this Musical Offering to King Frederick, and on the page preceding the first sheet of music, he inscribes: Regis Iussu Cantio Et Reliqua Canonica Arte Resoluta, meaning "At the King's Command, the Song and the Remainder Resolved with Canonic Art." an acrostic spelling "RICERCAR," the original name for the musical form now known as the Fuge. Bach also uses this title for the two fugues. Ricercar is also an Italian word meaning "to seek", which is appropriate since Bach doesn't quite write all the music. He leaves hints on how to complete the scores as musical puzzles for the King to solve.
One example of these puzzles is the work entitled "Canon a 2 (Cancrizans)". The original score looks like this:
Canon a 2 (Cancrizans)
The title "Canon a 2" implies it's a two-voice canon, but the score only shows one voice. There are hints in the score for solving the puzzle of the second voice:
- Cancrizan is Medieval-Latin meaning "to move backwards" literally crab-like.
- There is an extra clef at the end of the score, and it is backwards.
- The three flats at the end of the score are also facing backwards.
All of these hints strongly imply that the second voice (the follower) is the same as the first voice (the leader) only played backwards. What you listened to in the beginning was Canon a 2 (Cancrizan) as performed by the Stuttgarter Kammerorchester under the direction of Karl Münchinger. Listen to it again:
But note that since the second voice is the same as the first voice, only played backwards. We should be able to reverse the recording and the canon should still sound the same! Listen to the same canon being played backwards:
Now listen to the original canon once again. How much, on your same scale, did you enjoy it this time? Was it more? Significantly more? How likely are you to want to listen to the rest of the Musical Offering? For example by buying one of these two CDs?
If you are like most people, you found the second hearing much more enjoyable than the first. This is because your expectations, the context in which you have an experience, and how much you know about something all have a big effect on how much enjoyment you derive. Reading the story taught you something about the music, it served as a guide of what to look for. Sure, it helps that this is a musical masterpiece by the best baroque composer there is. But the effect works, even if the story is false.
Oh, I'm not saying that the above story didn't happen. I dressed it up a little, but the story is true. However, take a look at the Significant Objects project. They take an insignificant object (bought at a Thrift store) and ask a writer to make up a back story for it. Then they sell it on ebay. They are careful to disclose that the story is false, and they donate the proceedings to charity. But how much do the objects gain in value? This Russian Figurine that they bought for $3 was sold for $193.50!
In one experiment, scientists at Caltech and Stanford told people they would be tasting wines ranging in price from $5 to $90, and asked them to rate the wines. Unsurprisingly, the more expensive wines were rated higher than the cheap wines. The twister? All the samples were the exact same wine. Since people expected the more expensive wine to taste better, it tasted better.
So here is the trick I promised you. If you want to make an experience more enjoyable, find or create a backstory. It's better if the story is true and you believe it, but it works even if it's a made up story.
For much more information about the canons of Bach's Musical Offering, look here, or here.
- This is the letter of dedication that Bach sent to the King (quoted from The New Bach Reader, p. 226-8):
MOST GRACIOUS KING!
In deepest humility I dedicate herewith to Your Majesty a musical offering, the noblest part of which derives from Your Majesty's own august hand. With awesome pleasure I still remember the very special Royal grace when, some time ago, during my visit in Potsdam, Your Majesty’s Self deigned to play to me a theme for a fugue upon the clavier, and at the same time charged me most graciously to carry it out in Your Majesty’s most august presence. To obey Your Majesty’s command was my most humble duty. I noticed very soon, however, that, for lack of necessary preparation, the execution of the task did not fare as well as such an excellent theme demanded. I resolved therefore and promptly pledged myself to work out this right Royal theme more fully and then make it known to the world. This resolve has now been carried out as well as possible, and it has none other that this irreproachable intent, to glorify, if only in a small point, the fame of a monarch whose greatness and power, as in all the sciences of war and peace, so especially in music, everyone must admire and revere. I make bold to add this most humble request: may Your Majesty deign to dignify the present modest labor with a gracious acceptance, and continue to grant Your Majesty’s most august Royal grace to
Your Majesty’s most humble and obedient servant
Leipzig, July 7, 1747 The Author
[↩]
Proof that P=NP
So I was browsing Concrete Mathematics
- Specifically for N=1. It's in the margin of the book [↩]
The Two Envelopes Problem
A recent thread in reddit about the two envelopes problem reminded me of how unintuitive probabilities can be. There is a fundamental flaw with how the original post worded the problem:
You and I both have envelopes filled with money. My envelope contains either double or half the amount of money that’s in yours. If you want, I’m going to let you switch envelopes. Should you stay, switch, or does it not matter?
Stop right there. Read that again. Does that make sense to you? See if you can set up the experiment in the real world. Grab two envelopes and some money. Take $100 and put them in an envelope, then, uh... what do you do with the other envelope? Put $50 in it? Put $200?
The original poster then went ahead and solved assuming probabilities of 1/2. But I'm not really choosing between two equally likely options. I don't know the probability distributions!
A better wording for the problem (or a different problem if you're pedantic) would be:
There are two envelopes. One contains double the amount of money than the other. You choose one of them, I take the other. Now I offer you a choice between keeping your original choice or switching envelopes with me. Is it to your advantage to switch?
The answer should be obvious, it doesn't matter.
The Monty Hall problem
After all the positive feedback I got from Visualizing Bayes' theorem, I thought I'd post my explanation of the Monty Hall problem. I was fascinated for a while with this problem because at first it doesn't seem to make any sense. And most of the explanations I've seen have a magic feel to them. I've even seen people with math backgrounds argue against the result.
I think the problem has to do with most of the explanations mixing two very different probability classes. But I'm getting ahead of myself.
The Problem
The problem statement (from Wikipedia) is:
Suppose you're on a game show, and you're given the choice of three doors: Behind one door is a car; behind the others, goats. You pick a door, say No. 1, and the host, who knows what's behind the doors, opens another door, say No. 3, which has a goat. He then says to you, "Do you want to pick door No. 2?" Is it to your advantage to switch your choice? (Schrock 1990) [1]
If you are like most people, your gut feeling is going to be "it does not matter. There is a 50-50 chance that the car will be in the door I have already selected". Like most people, you would be wrong.
In order to solve this problem, you need to consider two very distinct pieces of information. One is "what state is the world in?", the other is "what events have occurred?". Let me elaborate.
The States of the world
When I deal with probabilities and get confused, I revert to counting. What are all the possible outcomes? What subset of those outcomes am I looking at? So let's look at all the posible states.
Suppose you're on a game show, and you're given the choice of three doors: Behind one door is a car; behind the others, goats.
Let's translate that to a simple diagram. We have three doors, let's label them A, B, and C. We also know that there is a car behind one of the doors, it can be behind door A, B, or C. So we have three possible configurations of the world:
The door with the car has been colored red. The possible states of the world are Sa (meaning the car is behind door A), Sb (car behind door B), and Sc (car behind door C).
Quick, what is the probability of the car being behind door A? Or to put it another way, what is the probability that the world is in state Sa? Note that these two questions are the same, but the latter reminds us of the possible states. It is easy then to see that
Now I'm going to ask you a very different question. Assume that instead of playing, you are observing your friend play the game. What is the probability that he will pick door A? Did you say 1/3? Of course you did, there are three doors and he must pick one. However, and this is really important, these probabilities are completely independent of the probabilities above!
Think of it this way. If two doors had cars behind them instead of just one, would that change the number of states the world can be in? Would it change the probability of your friend choosing door A? What if all doors had cars? Now there is just a single state for the world, but your friend can still choose door A with 1/3 probability!
If we now say that A is the event of your friend opening door A, we can easily see that
which is just saying each door has an equal probability of being opened.
The trick to solving this problem is that you are dealing with two different classes of probabilities. One is the probability that the world is in a given state (a priori), the other is that a participant (you or Monty) chooses any given door. If you can keep these two classes of probabilities separate, you will be able to easily solve this problem.
Let's see what happens once you have made the choice. Let's assume you chose the door labeled A.
What does Monty do?
Monty is, of course, the host of the game show. And he is trying to screw you. He doesn't want you to get the car. He also happens to know where the car is, or in other words, he knows the state of the world. You on the other hand, are only guessing. You chose door A with probability 1/3, now he gets to choose a door. But there are only two doors left. He must choose either door B or door C.
So how does Monty choose? What is the probability that Monty will open the door labeled B? Here's what the world looks like to Monty:
Door A has been chosen, he must choose between doors B and C. Were he to choose randomly, each door would be equally probable,
The little m's are a reminder that this is Monty's choice, not your original choice. If you wanted to be pedantic you could add P(Am) = 0 since Monty can never choose door A (you chose that one).
But he knows better than to choose randomly, he knows whether we're in Sa, Sb, or Sc! How he chooses will depend on what the state of the world is. If we are in Sa, it doesn't matter what he chooses, he'll choose B or C with equal probability as neither has a car[2]. That is to say "given that we are in state Sa, Monty chooses door B with probability 1/2", in other words:
If we are in state Sb, Monty will never choose door B, that would be giving away the prize.
And finally, if we are in state Sc, Monty will always choose door B.
Your turn
And now it's your turn to make a decision. Do you stay with your original choice of door A? Or do you switch and choose door C?
First of all, does it matter? Is there any difference whether we switch or not? The answer is a resounding YES! Monty gave away information about the state of the world by choosing door B. We can use that information.
What we are really trying to figure out is this: "what configuration is the world in?" Monty knows, he used that information to choose door B. Now we have to ask ourselves, "given that Monty chose door B, what is the probability that the world is in state Sa versus the probability of the world being in state Sc?" Note that we have eliminated Sb because Monty has already opened door B and there was no car!
Here is where we can apply Bayes' formula to get an answer:
and plugging in the values we have already computed:
Which means we have a 1/3 chance the car is behind our original choice of door A. Note that this 1/3 probability is different than the original P(A) = 1/3 we had computed. It ends up being the same number, but it is really a different probability!
What about the car being behind door C? What is the probability that we are in state Sc, given that Monty chose door B?
and plugging in the values we get:
Which means we have a 2/3 chance the car is behind the other door (door C). Therefore we should switch.
Does it matter if Monty knows?
The only reason we managed to gain any information from Monty's choice of door B is that he knows the state of the world and acts differently depending on what state is the correct one. If Monty didn't know, he would have been choosing randomly between doors B and C and we would not have gained any information (except that Sb is not possible since there was no car behind door B).
If Monty always chooses door B when neither B nor C have the car, we would not have gained any information when he opens door B, but we would gain information if he opens door C (do you see why?).
Note that it is still to our advantage to switch doors, since in this case the probabilities for the states Sa and Sc are the same (1/2). And if we don't know whether Monty knows or not, we might get an advantage from switching.
- If you are really pedantic, the mathematically correct definition of the problem is: "Suppose you’re on a game show and you’re given the choice of three doors. Behind one door is a car; behind the others, goats. The car and the goats were placed randomly behind the doors before the show. The rules of the game show are as follows: After you have chosen a door,the door remains closed for the time being. The game show host, Monty Hall, who knows what is behind the doors, now has to open one of the two remaining doors, and the door he opens must have a goat behind it. If both remaining doors have goats behind them, he chooses one randomly. After Monty Hall opens a door with a goat, he will ask you to decide whether you want to stay with your first choice or to switch to the last remaining door. Imagine that you chose Door 1 and the host opens Door 3, which has a goat. He then asks you “Do you want to switch to Door Number 2?” Is it to your advantage to change your choice? (Krauss and Wang 2003:10)" [↩]
- This is important, if he doesn't choose either door randomly, you gain information asymmetrically. Keep reading. [↩]
Visualizing Bayes’ theorem
I recently came up with what I think is an intuitive way to explain Bayes' Theorem. I searched in google for a while and could not find any article that explains it in this particular way.
Of course there's the wikipedia page, that long article by Yudkowsky, and a bunch of other explanations and tutorials. But none of them have any pictures. So without further ado, and with all the chutzpah I can gather, here goes my explanation.
Probabilities
One of the easiest ways to understand probabilities is to think of them in terms of Venn Diagrams. You basically have a Universe with all the possible outcomes (of an experiment for instance), and you are interested in some subset of them, namely some event. Say we are studying cancer, so we observe people and see whether they have cancer or not. If we take as our Universe all people participating in our study, then there are two possible outcomes for any particular individual, either he has cancer or not. We can then split our universe in two events: the event "people with cancer" (designated as A), and "people with no cancer" (or ~A). We could build a diagram like this:
So what is the probability that a randomly chosen person has cancer? It is just the number of elements in A divided by the number of elements of U (the Universe). We denote the number of elements of A as |A|, and read it the cardinality of A. And define the probability of A, P(A), as
Since A can have at most the same number of elements as U, the probability P(A) can be at most one.
Good so far? Okay, let's add another event. Let's say there is a new screening test that is supposed to measure something. That test will be "positive" for some people, and "negative" for some other people. If we take the event B to mean "people for which the test is positive". We can create another diagram:
So what is the probability that the test will be "positive" for a randomly selected person? It would be the number of elements of B (cardinality of B, or |B|) divided by the number of elements of U, we call this P(B), the probability of event B occurring.
Note that so far, we have treated the two events in isolation. What happens if we put them together?
We can compute the probability of both events occurring (AB is a shorthand for A∩B) in the same way.
But this is where it starts to get interesting. What can we read from the diagram above?
We are dealing with an entire Universe (all people), the event A (people with cancer), and the event B (people for whom the test is positive). There is also an overlap now, namely the event AB which we can read as "people with cancer and with a positive test result". There is also the event B - AB or "people without cancer and with a positive test result", and the event A - AB or "people with cancer and with a negative test result".
Now, the question we'd like answered is "given that the test is positive for a randomly selected individual, what is the probability that said individual has cancer?". In terms of our Venn diagram, that translates to "given that we are in region B, what is the probability that we are in region AB?" or stated another way "if we make region B our new Universe, what is the probability of A?". The notation for this is P(A|B) and it is read "the probability of A given B".
So what is it? Well, it should be
And if we divide both the numerator and the denominator by |U|
we can rewrite it using the previously derived equations as
What we've effectively done is change the Universe from U (all people), to B (people for whom the test is positive), but we are still dealing with probabilities defined in U.
Now let's ask the converse question "given that a randomly selected individual has cancer (event A), what is the probability that the test is positive for that individual (event AB)?". It's easy to see that it is
Now we have everything we need to derive Bayes' theorem, putting those two equations together we get
which is to say P(AB) is the same whether you're looking at it from the point of view of A or B, and finally
Which is Bayes' theorem. I have found that this Venn diagram method lets me re-derive Bayes' theorem at any time without needing to memorize it. It also makes it easier to apply it.
Example
Take the following example from Yudowsky:
1% of women at age forty who participate in routine screening have breast cancer. 80% of women with breast cancer will get positive mammograms. 9.6% of women without breast cancer will also get positive mammograms. A woman in this age group had a positive mammography in a routine screening. What is the probability that she actually has breast cancer?
First of all, let's consider the women with cancer
Now add the women with positive mammograms, note that we need to cover 80% of the area of event A and 9.6% of the area outside of event A.
It is clear from the diagram that if we restrict our universe to B (women with positive mammograms), only a small percentage actually have cancer. According to the article, most doctors guessed that the answer to the question was around 80%, which is clearly impossible looking at the diagram!
Note that the efficacy of the test is given from the context of A, "80% of women with breast cancer will get positive mamograms". This can be interpreted as "restricting the universe to just A, what is the probability of B?" or in other words P(B|A).
Even without an exact Venn diagram, visualizing the diagram can help us apply Bayes' theorem:
- 1% of women in the group have breast cancer → P(A) = 0.01
- 80% of those women get a positive mammogram, and 9.6% of the women without breast cancer get a positive mammogram too → P(B) = 0.8 P(A) + 0.096 (1 - P(A)) = 0.008 + 0.09504 = 0.10304
- we can get P(B|A) straight from the problem statement, remember 80% of women with breast cancer get a positive mammogram → P(B|A) = 0.8
Now let's plug those values into Bayes' theorem
which is 0.0776 or about a 7.8% chance of actually having breast cancer given a positive mammogram.
Is that possible?
I normally read the good math bad math blog, where Mark Chu-Carroll debunks crackpots that try to hide their crazyness behind bad math. A while ago, he posted an article called "Why Math?", where he discusses how math allows you to "without ambiguity, prove that something is true or false".
While I agree with Mark, I think it's not completely clear from his post the importance of math's role in deciding what to believe.
One comment in particular inspired me to write this post.
Statements of the form "___ is impossible." strike me as deeply unscientific and dogmatic.
See, math is a formal system for thinking logically. The heart of math lies in being able to prove things from assumptions. So in that sense, if the math is done right, Mark's remark "without ambiguity, prove that something is true or false" is spot on.
However, the assumptions need to be true or your whole argument is invalid, no matter how good the math is.
But going back to "___ is impossible", I think there are different levels of "impossible" that we need to be concerned about.
We can classify impossible things in three categories: logically impossible, physically impossible, and technologically impossible.
The logically impossible
To understand the first category, we need to resort to some philosophical bullshit. Back in the day when people didn't have reddit and used to wander around in their togas thinking whether we could think at all, the great Aristotle proposed what he called his three laws of thought. These form the basis of logic and if you think about them, they make perfect sense. The first law is called the law of identity, and it just says an object is equal to itself. The second law is the law of noncontradiction and it says that nothing can both have a property and not have it at the same time. The third law is the law of excluded middles and it says that objects either have a certain property or they don't
I particularly like Avicena's description of the law of noncontradiction:
Anyone who denies the law of non-contradiction should be beaten and burned until he admits that to be beaten is not the same as not to be beaten, and to be burned is not the same as not to be burned.
This is where math helps. Math allows you to follow arguments to their logical conclusion and either prove or disprove them. It's formalized thinking, and it's full of little shortcuts and notation that allows you to be efficient in reaching your conclusions and in communicating those conclusions to others.
If you find something to be logically impossible, you've found a real impossibility. No way around it. Time travel is the best example of a logical impossibility. If you travel back in time to a place (and time) you have never been before, you would violate the law of noncontradiction (you were both there and not there). That's why sophisticated science fiction writers like Michael Crichton always have the travelers go to a parallel universe
The physically imposible
Some things however, are not logically impossible, but they violate the laws of physics. This is slightly harder to detect, since our understanding of the laws of physics changes and it has been known to be completely wrong. But if you claim that something that violates the laws of physics is possible, the burden is on you to convince us that the laws of physics are wrong. Not an easy feat!
One example of this would be the claim that you can travel faster than light. Unless you're willing to debunk Poincaré's theory of relativity, you're going to have trouble having anyone believe you.
The technologically impossible
Other things don't violate either the laws of logic (math) or the laws of physics, yet they are beyond our current reach. This is the weakest level of impossibility because it could be just a matter of time before we get there. Almost all current technology would have fallen in this category only a century ago. Just imagine trying to explain the Internet and iPhones to people of the 1800's, they would have certainly shouted "Witchery!".
In conclusion, statements of the form "___ is impossible" don't need to be unscientific and dogmatic.
Simple Guide to Complexity Theory
After reading Jeff's terribly misguided post about NP-completeness I thought to myself: "If Jeff, who seems to be completely clueless about complexity theory, can write a blog post about it then so can I."
So without further ado, here's ob's complex guide to simplifying complexity theory.
First of all let's get the definitions out of the way.
Turing machine: An idealized computer, with infinite memory, an infinitely fast cpu, and unlimited bandwidth. It's a mathematical model of computer so it can kick your Core 2 Duo's sorry little ass faster than you can say Pentium. (update: I originally wanted to make the point that bandwidth and cpu speed are irrelevant, but it seems to have confused more than clarified.)
Problem: In complexity theory, a problem is really a decision problem. It has a simple yes/no answer. You don't ask "take this list and sort it and print the last ten items" that's not a decision problem. You do ask "does this program, given this input, produce the last ten items of the sorted input?".
(update: Although the sort problem as outlined here would be a valid decision problem, it is confusing since just changing my "last ten items" to "last C items" where C is a function of n would make it not be a decision problem. Better to use some other example, like "is the number given prime?")
n: Size of the input for the turing machine. E.g. if your turing machine is sorting strings, like in the example above, n is the number of symbols that it takes as input.
T(n): Number of steps (i.e. instructions) that a turing machine must execute to solve a problem with input of size n.
Polynomial Time: When T(n) can be expressed as an equation of n, and possibly some constants, using only addition, subtraction, multiplication, and constant non-negative whole number exponents. E.g. n² is a polynomial while 2ⁿ is not.
Non-deterministic turing machine: A turing machine that can, at every branch point, take all possible branches in parallel. We call this guessing the optimal answer because, since the turing machine takes all branches, it must take the optimal branch too. If any of the parallel turing machines finds an answer, the non-deterministic turing machine stops and gives that answer (this means that it's ok for some branches to never end).
So take your already idealized computer from above and make it able to reproduce itself on every branch point. I.e. it can follow all possible decisions in parallel.
P: The class of problems that can be solved by a turing machine in polynomial time.
NP: The class of problems that can be solved by a non-deterministic turing machine in polynomial time.
Reducing a problem to another: Imagine you have two problems, P1 and P2. You know something about P1 (e.g. that it belongs to NP). Now you want to prove some property of P2, for instance, that it belongs to NP as well.
One technique is to show that if we could solve P2 in polynomial time (i.e. P2 belongs to P), we could use that answer to solve P1 in polynomial time. This would mean that P1 belongs to P which is a contradiction. This technique is called reductio ad absurdum. (update: I completely botched this and commenter Bibi correctly called me on it. Here's an attempt to clarify a reduction: if you want to solve an instance of P2, you convert it to an instance of P1, and then solve P1 to get an answer. Thus, you've reduced P2 to P1. How's that?)
NP-complete: We say a problem is NP-complete if it satisfies two properties: 1) it belongs to NP, and 2) every other problem that belogs to NP can be reduced, in polynomial time, to it.
This means that if we come up with a solution for an NP-complete problem that runs in polynomial time in a deterministic turing machine (i.e. belongs to P), any other problem in NP can be solved in polynomial time by first reducing it (again, in polynomial time) to this problem, and using our solution. We would have proved that P = NP and we would have also won (pinky to corner of mouth) one million dollars.
NP-hard: A problem P1, that is so hard, that even though we can prove number two above, we can't prove number one. This means we know P1 to be just as hard as anything in NP and possibly harder, but we don't know if P1 is in NP or not. P1 is very likely to require exponential time.
(update: I stand by my definition of NP-hard. Although not being able to prove #1 is a sufficient condition, it is not necessary. All problems in P are in NP, and yet we call them P, not NP. Thus, even if all problems that are NP-complete are also NP-hard, it's uninteresting to call an NP-complete problem NP-hard. The point of calling a problem NP-hard is that, it's really hard! Even if it turned out that P = NP, an NP-hard problem might still be hard!)
So there you have it, go impress your friends. I hear that "hey, baby! your love is NP-hard to get" is a very successful pickup line at pubs around M.I.T.
The case against snippets
Back when TextMate was relatively new and that famous video of ruby on rails was making the rounds. I watched in amazement with the rest of the nerds as code flew around the screen. I had caught Snippet Fever.
After using TextMate for a while I became addicted to snippets. The basic idea of a snippet is that you can write a few characters and they expand to whatever you want. For example, you can type: 'fl', hit Tab and TextMate will write:
for(int i = 0; i < ... ; i++) { ... }
Where ... is where the insertion point will be each time you hit tab. You can do the same with Emacs in many different ways: Emacs skeletons, the snippet.el plugging, hand-coded elisp, etc. The point of this post, however, is not to show all the different ways that you can get snippets. The point is to ask whether it's worth using snippets at all.
Snippets eliminate the need to type recurrent idioms. If you have to write accessors, it's very pleasant to type 'set', hit tab and watch the screen fill with 20 lines of code that just wrap a field in a class with a setter function. But this is fixing the problem in the wrong place.
The fundamental problem is that the language
Imagine English had no pronouns so if I wanted to tell you a story about my friend Tim and me, I had to write:
Tim had called Oscar to ask Oscar if Oscar could lend Tim the book that Oscar had bought the day before. Oscar told Tim that Oscar was still reading it, but that Oscar would be happy to lend Tim Oscar's book when Oscar was done with the book so that Tim could read it.
The above paragraph is too verbose. It's hard to write. Snippets would help me write it by automatically filling all the appropriate places with "Tim" and "Oscar".
If the language you are using is so verbose that you need snippets, how about fixing the language?
Even on languages that don't allow fixing the syntax you can still do something.
For example, in C, if you find yourself typing a for loop to access a list over and over again:
for (int i = 0; i < length(list); i++) { }
Make a small pre-processor macro that abstracts that:
#define EACH(list) for (int i = 0; i < length(list); i++)And now you can write:
EACH(list) printf("%s\n", list[i]);
And since code is usually read many more times than it is written, you have helped make the source base a little better.
Another useless C99 tidbit
From page 18 of the C99 standard:
All occurrences in a source file of the following sequences of three characters (called trigraph sequences) are replaced with the corresponding single character.
??= # ??( [ ??/ \ ??) ] ??' ^ ??< { ??! | ??> } ??- ~No other trigraph sequences exist. Each ? that does not begin one of the trigraphs listed above is not changed.
Ok, so take the following C program:
??=include <stdio.h> int main(int argc, char *argv??(??)) ??< printf("hello world\n"); ??>
And compile it with the -trigraphs switch to gcc:
dirac src $ gcc -trigraphs -o trigraphs trigraphs.c dirac src $ ./trigraphs hello world
Combined with this you could seriously obfuscate your C code.
Hidden Gems in C99 (1)
After some late night reading of the C99 spec, I've found quite a few hidden gems. I'm going to start posting some of these. Since it's late, I'll just post a teaser.
On page 64 of the C99 standard it says:
In all aspects of the language, the six tokens
<: :> <% %> %: %:%:behave,respectively,the same as the six tokens
[ ] { } # ##except for their spelling.
Really? Then let's try this program:
%:include <stdio .h> int main(int argc, char *argv<::>) <% printf("hello world\n"); %>
Compile it an run it:
dirac src $ gcc main.c dirac src $ ./a.out hello world
Whaddaya know... I know, I know... useless. Wait for the next post then.