We both know it's been forever since I posted on LJ. This
one's too long for Twitter and doesn't mesh well with my
mostly-Lisp blog. 'Nuff said.
I've started reading The Golden
Ticket: P, NP, and the Search for the Impossible by Lance
Fortnow. So far, I'm enjoying the material. However, he keeps
smacking into one of my biggest math peeves: Proof is Panacea.
Before I explain that or mention how it relates to Fortnow's
book, let me tell you where Numbers smacked
into this peeve.
One, Episode Five guest-starred Neil Patrick Harris. NPH was
close to a proof of the Riemann
Hypothesis. The Riemann Hypothesis is closely linked to the
distribution of prime numbers. Prime numbers are intimately
involved in much of the encryption technology in use today (even
more so back when that episode first aired).
In the episode, NPH's daughter had been kidnapped by some
baddies that were demanding a complete proof of the Riemann
Hypothesis as ransom. Part of the premise of the episode was that
with such a proof the kidnappers would be able to decrypt any
secure internet transactions. Modern civilization would fall
At the time, eyelid asked me,
happen if someone could prove the Riemann Hypothesis? My
thought at the time (and still), is absolutely nothing in any sort
of short timeframe beyond winning the author a Millenium
If there is anything you can do to break today's encryption
schemes once you know the Riemann Hypothesis to be true, then you
can already do that just by guessing that the Riemann Hypothesis
is true. Sure, there is a small chance that there will be some
new tool or new revelation that comes out of the manner in which
the Riemann Hypothesis is proven (or falsified) that might
eventually make finding particular primes easier. I consider that
a small chance and only after years of delving.
It is a sad truth that many of the great proofs are
non-constructive. One of the easiest ones to follow is Euclid's
proof of the Infinitude of the Primes. Suppose for a moment
that there aren't infinitely many primes. If that were the case,
there would only be N of them for some (possibly large) number N.
If you multiply all of those primes together you get a number that
is divisible by every prime number. If you add one to that
number, now you have a number that has remainder one when divided
by any prime number. So, either this number is prime and wasn't
on your list, or you missed some prime that divides into this
number. It must, therefore, be impossible to have a finite list
of all of the prime numbers.
What can you do now that this has been proven that you couldn't
do before this was proven? You can prove things that depend on it
being true, but what can you do. The answer is
nothing new. You can't even name a single prime number that you should have had on your list. You can't tell whether any given number that didn't make your list is prime or not. You can't tell how many primes you might have missed. Anything you can do because we've proven
there are infinitely many primes, you could have done with just
the supposition (or hope) that there were infinitely many
I can understand how a TV drama might ignore that inconvenient
truth so it won't fizzle the tension in your plot, but I can't
forgive Fortnow the same sin. Fortnow says over and over again
that if you can prove that P =
NP then you can do all kinds of things easily that everyone
else still considers hard. You'll be able to optimally route your
Travelling Salesman, you'll be
able to crack my
public key, you'll be able to optimally fit your stuff
into the minimum
number of moving truck trips, and you'll be able to play a perfect game of Tetris if you know what order the pieces will come out.
First, as does Fortnow, I consider it very unlikely that P does
equal NP. Second, even if P = NP, I'd only give it about a one
in fifty chance of being provable. Third, if it's provable, I'd
give it a one in one thousand chance that the first proof will be
constructive. Fourth, even if it is constructive, I'd only give that
a one in ten chance of showing any way to find an algorithm in P
to solve any given problem.
Fortnow knows way more about P vs. NP than I do. Maybe he
knows something that he's not letting on about that guarantees
that the only way to prove P = NP is by demonstration. If that's
the case, I sure wish he'd tell me. But, I think he's either just
caught up in how cool it would be if NP were P or he's just
building drama by sweeping truth under the rug.
Suppose that you're travelling with four kids in the car. It's
getting to be time for lunch and you want to exercise the kids a bit.
Ohio has very nice rest areas, but you think a mall would be a better
fit. So, you search Apple Maps for a mall.
You've just passed the I-90/I-75 interchange. You don't want to go
back for all of the malls on the west side of Toledo, so you settle on
the Woodville Mall.
You get there to discover that the Woodville Mall
is all but condemned.
Fortunately, the babies have dozed off again. You need gas, but
the gas stations near the
mall are $.15/gallon more than the
ones just off the highway were. So, you figure there will be some gas
stations near the Sandusky Mall. You head out.
You get to point B and haven't seen a gas station. You search
Apple Maps. It says that
Coles Energy, Inc. is at around point
Shumaker Gary BP is at point C. You decide that Coles
Energy is probably a gas company rather than a gas station. You head
back to Shumaker's. You find that Shumaker's is a BP distribution
station. There are six tanker trucks and zero pumps.
You stop at a nearby restaurant. You explain to the lady behind
the counter that you're just passing through looking to get to the
Sandusky Mall and are in dire need of gasoline. She says,
Hmmm... and freezes up. You're thinking,
nearest gas is going to be 30 miles back toward Toledo.
Finally, someone else jumps in and points you back toward point D.
There are three gas stations right near there which did not show up on
Apple Maps. Coles Energy was right across from the one you stopped at.
Coles, indeed, could provide for you if you had needed propane, but not
petrol. You got gas. Now, off to the mall.
Now, you are flipping back and forth between Apple Maps and Google
Maps to compare. Google Maps had Shumaker's on it. It also had one
of the three gas stations that had been right on your path. Of
course, somewhere in here, Apple Maps quit giving you spoken
directions. So, you missed the turn at point B in the previous map. You kick Apple Maps back into action and it leads you through the path shown to point C.
Point C is not anywhere near the actual Sandusky Mall. It is out
in the sticks. You passed through a closed campground and past a few
farms and through some sparse neighborhoods to get to point C. There
is no mall there at all. There are dirt roads. There is a bay.
Of course, you're way far away from decent cell reception now.
Neither Apple Maps or Google Maps can properly locate you. You
track down an intersection that's big enough to register on Google
Maps and start heading to what you hope is the real mall with
Google Maps now.
Now, there is a gorgeous rainbow over the road and an Ohio trooper
that just pulled over to start clocking cars. You were also expecting
the exit to be labelled Milan Road. You miss the turn at point B and
turn around at point C.
You make it almost to point D and fear that what was labelled
Sandusky Mall on Google Maps and the exit you took off of
Ohio-2 is really just a Meijers store. Thankfully, you just gave up
a few hundred feet too early. The mall does exist, is open, does
sell food, and does have a children's play area. Now, it's dinner time.
Having been awake for 34hrs now, you send your spouse in with the kids while you take a somewhat
cramped nap on the floor of the van. The nap is surprisingly
pleasant until your boss calls to remind you that you need to turn
in your timecard sometime in the next 18hrs.
Here's the situation. You're in an all-day meeting at work. It comes time to order the pizza for lunch. A quick survey of the 20 people present reveals that four of you are vegetarian. Obviously, since 20% of the people are vegetarian, 20% of the pizzas should be meat-free.
Of course, this fails to take into account the fact that some non-vegetarians will have
just a slice of the meat-free pizza.
There should be a name for this problem.
The first thing that comes to mind for me is the law of the excluded middle. According to the classical laws of thought, every proposition is either true or not true. There is no middle ground. For this situation, things would have to be framed as: That every person either only eats meat-pizza or only eats non-meat-pizza. That doesn't quite work for me. This suggests the name The Law of the Excluded Eaters.
The next thing that comes to mind is Bayes' Theorem. According to Bayes' Theorem, the probability that someone is vegetarian given they are eating cheese pizza P(V|C) is equal to the (prior) probability that someone is vegetarian P(V) times the probability that someone is eating cheese pizza given they are vegetarian P(C|V) divided by the (prior) probability that someone is eating cheese pizza P(C). The pizza problem is a common fallacy that makes grokking Bayes' Theorem tough for people. The common fallacy is called Berkson's Paradox and is related to the Prosecutor's Fallacy. People inadvertently equate the probability of eating cheese pizza P(C) with the probability that one is vegetarian P(V). This suggests the name The Bayesian Pizza Paradox.
The next thing that comes to mind for me is a simple Venn diagram. The problem assumes that the set of people who eat meat-pizza and the set of people who eat non-meat pizza have zero members in common. The intersection is the Null Set. This suggests the name The Null Intersection Hypothesis.
I like the name, too, because of its association with the Null Hypothesis from statistics. It suggests that every group-pizza order is a sociological experiment where the assumption going in is that meat eaters will eat only meat-pizza and non-meat eaters will eat only non-meat pizza.
The Venn diagram concept also brings up the Inclusion-Exclusion Principle. By that principal, the number of people in the who eat either sausage pizza or cheese pizza |S ∪ C| is equal to the number of people who eat sausage pizza |S| plus the number of people who eat cheese pizza |C| minus the number of people who eat both sausage and cheese pizza |S ∩ C|. It is common for people to forget to subtract that last term. This works when the intersection is empty. This suggests the name The Exclusion-Exclusion Principle.
That same principle here is also related to the Triangle Inequality. By the triangle inequality, the number of people total is less than or equal to the number who eat only meat pizza and the number who eat only non-meat pizza. This name is suggestive in shape. But, I'm not sure the Pizza Slice Inequality really works for me.
Another thing that comes to mind for me is the 80-20 rule. In this case, though, it would be the 80-80 rule: 80% of the people eat 80% of the pizza. It doesn't really work for me though. It doesn't fit well enough.
Another thing that comes to mind is proportional, representative democracy. One person = one vote. This suggests the name Representative Pizzocracy. But, it's not mathy enough for me.
Unless someone has a better suggestion, I'm going with the Null Intersection Hypothesis.
In a radio news story about the on-going drought, some water company representative said that last month's water usage (in whatever area he was talking about... I don't remember... it doesn't matter here...) was 300 million gallons.
We have many, many commonly used subdivisions of gallons:
- 1/4th of a gallon is a quart
- 1/2 of a quart is a pint
- 1/2 of a pint is a cup
- 1/8th of a cup is an ounce
- 1/2 an ounce is a tablespoon
- 1/3rd of a tablespoon is a teaspoon
We have many units of liquid measure larger than a gallon
when it's wine or ale.
- One rundlet is 18 gallons of wine
- One firkin is 84 gallons of wine or 8 gallons of ale
- One tierce is 42 gallons of wine
- One barrel is 31.5 gallons of wine or 4 firkins of ale or 42 gallons of oil
- One hogshead is 63 gallons of wine or 1.5 barrels of ale
- One pipe is 1.5 firkins of wine
- One tun is 2 pipes of wine
This is a total mess, especially needing to know if you're talking about wine versus ale. But, if we're talking about hundreds of millions of gallons of water, shouldn't we have some unit bigger than a gallon?
Maybe millions of gallons would be used too infrequently for people to remember how many gallons are in the units. But, I think we should start using metric prefixen:
- 300 megagallons of water
- 16 teradollars of national debt
- 50.9 to 50.4 megavotes
I woke up this morning feeling very nostalgic for an apartment in which I used to live. It was a really small apartment. I lived there for awhile with eyelid and before that with _xis. I have very distinct memories of this place. All of these memories are very happy. This morning's memory was being there with eyelid.
This is the apartment layout.
As you can see, it is very small. As you can also see, there is a large grayed out area of the apartment. It is left blank since I have never seen that part of the apartment.
In all of my memories of this place, I am sitting at the table next to Scoot or eyelid or _xis, laughing and talking, while one of us is cooking at the stove. Now, it's fair to point out here that the last sentence probably wasn't interpreted as intended because of basic assumptions about how things work. At no time in these memories were there more than two people in the apartment, yet there were two people at the table. One of whom was also at the stove cooking. Simultaneously.
You see, this apartment does not exist. I have been dreaming these memories for more than fifteen years. Every time that I
remember this place, I spend the next several waking hours trying to be sure there really was no such place. The memories are so happy and so real and so temporally impossible and so spatially paradoxical.
A recurring dream. Of happy memories. With dear friends.
There has been a substantial push by the Republicans in the
Minnesota legislature to amend the state constitution to ban same-sex
marriage (which is already against Minnesota state law). Now, it's no
secret that I am absolutely for marriage equality. But, this whole
thing has gotten me thinking more about the legal status of being male
or being female.
It is 2011. I have given up hope that anyone in my lifetime will
invent a good way to package plastic wrap for home use. But, it has
been illegal since 1920 to keep women from voting. It has been
illegal since 1964 to discriminate in hiring on the basis of sex.
It has been decades (not enough, but decades) since women needed
their husband's permission to open a bank account. Since 1998, it
has been illegal for me to sexually harrass people of either sex.
If I walked into the DMV today and told them that my driver's
license has been wrong about my sex for all of these years, what would
happen? They certainly wouldn't change it without my birth
certificate. If I alleged that that was wrong or alleged that I could
not find it, where would I be? Who gave the DMV the right to define
what sex I am?
Why does it make any difference to the government (especially
small government and
that I am male?
The only answers I have are that if I am (legally) male:
- I can be drafted into combat posts.
- I can be penalized for entering women's restrooms (maybe?).
- I am not allowed to marry a male.
I can see the political expedience of the first. I can see the
convenience of the second. I've got nothing for the third.
So, I spent too much time today trying to figure out why this C++ code worked fine:
std::set::iterator found = m_transactionIDs.find(id);
if (found != m_transactionIDs.end())
else if (someOtherComplexCondition)
When changing it to this gave me a core dump with a stack trace
of nothing but Ada:
std::set::iterator found = m_transactionIDs.find(id);
if (found != m_transactionIDs.end());
else if (someOtherComplexCondition)
( Peek here for the answer and subsequent rant...Collapse )
Or, is there some legitimate reason for this to be legitimate?
I thought certainly either the large company for which I work
or the large government agency that is our customer would have
put out a press release about the news that prompted the following
story. Alas, I can find no such news stories on
website or with Google.
So, I'm going to be stupidly vague in the following.
Last Tuesday, our customer made it to the end of a multi-year,
multi-faceted process that ended in a green-light for our software to
be installed at all of the sites instead of just the key test sites.
To celebrate this milestone, there was to be an after work, drinks
and appetizers shindig at a nearby restaurant on Wednesday.
Knowing that there would be many people at this event that
I have not properly met from my little corner of the cube farm, I
dressed to impress. Thinking the red power-tie was a bit too
formal (and not enough red), I consciously chose to wear a red
dress shirt and tan pants.
Unbeknownst to me, the restaurant waitstaff uniform is a
red dress shirt and tan pants.
When I arrived, my boss's boss (or my boss's boss's boss, depending
on which direction you orient the matrix-management chart) started
trying to order more appetizers from me.
Go first impressions!
Now, I am sure that he will never forget me, but he may
always be uncomfortably embarrassed near me. Not the kind of
impression I was hoping to make.
A month ago, a friend posted the following problem on Facebook. I just noticed it this week.
The goal is to find the exact length of the radius
I love this kind of math problem. It has a bunch of features that make it a great, toy math problem.
- It looks like it’s going to be easy, but at the same time seems at a glance to not have enough information
- It looks like a geometry problem but only requires that you know:
- All radii of a circle have the same length
- A radius to a point where a tangent line touches the circle is perpendicular to that tangent line
- It requires only very basic algebra:
- Pythagorean theorem
- Solving quadratics
- The numbers in the problem are small, non-zero integers
I spent the next 25 minutes and six pieces of paper working the problem. About 20% of the time that I spent was rechecking my work. Why did I bother rechecking my work on a toy problem?
Warning: Spoilers ahead. If you like this kind of problem, stop reading now and play with it first.
See my website for the rest of this article