I self-identify as a feminist.I think human males in general should self-identify as feminists. If we want to live in a society that is as technologically and scientifically advanced as can be, we must support feminism.
By "feminist," I don't mean that someone who believes that males and females are identical. Obviously they aren't. And I don't mean that that there aren't innate biological differences, some of which will result in statistically significant differences in the general population. Such differences indeed exist.
By feminist I mean someone who supports identical rights for people regardless of gender. I also believe that we should encourage females to pursue whatever professions, occupations and hobbies that they want and of which they are capable and that we should discourage negative stereotyping about lack of ability.
I don't self-identify as a feminist out of some deep ideological grounding. I don't have any strong ideological affinity with most of the feminist movement. Sure, equality in the abstract is nice. However, it is clear that stereotypes about females negatively impact on everyone. And so, I support feminism, not out of some deep belief, but out of simple self-interest.
How many women have become housewives or secretaries who might otherwise have been the next Barbara McClintock or Emmy Noether but for the fact that they were mistreated and told that math and science were for men? I don't know. But I do know that, for each of the women who were discouraged, there is at least one more interesting theorem, one more cool biological fact, one more interesting astronomical phenomenon that society missed out on. And some of those would have gone on, not just make interesting discoveries but to make practical, helpful discoveries. I have trouble keeping count how many friends and relatives I've lost due to cancer and other illnesses. How many of them would still be alive today if the right little girl hadn't been told that she couldn't do math or that science was for the boys? I don't know, but I can guess that it is probably more than one.
I'm a feminist not because I'm a good person who cares about equality, but because I'm a self-interested person who wants to learn and benefit from everyone I can. I want to live in the best, most technologically advanced society that I can. Therefore, I am a feminist.
Wednesday, June 29, 2011
Tuesday, June 28, 2011
What is P ?= NP and why should you care?
After my last blog post, readers remarked that they had no idea what
"P ?= NP" was and that I had completely failed to explain what I was talking about. They are correct. This entry is to remedy that problem.
First an analogy: Suppose you have a jigsaw puzzle. Assembling the puzzle correctly is difficult. But, if someone has the puzzle completed, one can generally tell at a glance that the puzzle is correct. (This isn't strictly true if you are dealing with someone like me who as a little kid would sometimes shove the pieces to fit in where they didn't belong. If one does this to sections that depict sky and clouds, it can be quite hard to tell that it is wrong.) But it seems that it is very difficult to tell how to assemble a puzzle. Moreover, it isn't even clear if one has all the pieces of the puzzle until one is nearly done with the puzzle. It can be a very frustrating experience to be nearly done with a puzzle and then realize that pieces are missing. What if there were a way to tell just from looking at the jumbled pieces in the box if one had the all pieces? Whether P is equal to NP is essentially asking if this is possible. The general consensus among computer scientists is that P is not equal to NP which means that puzzle-solvers are out of luck.
Let's break this down further. P is the set of types of puzzles that can be essentially solved quickly. So for example, "Is a given integer even or odd?" is a problem that lies in P. Given an integer, one can just look at the leading digit and see if it is even or odd. (I'm assuming that our integers are written in base 10). Similarly, the problem "given integers a and b, does a divide b?" is in P,;all one needs to do is divide a into b and see if there is a remainder. But not everything is necessarily in P. For example, the question, "is a given integer composite?" is not obviously in P, since checking requires successive search for divisors.
But, there is a larger class of problems, NP, which are problems which, if they have an answer of "yes," one can quickly convince someone else of the answer if one has the right information. In this context, "is an integer composite?" is in NP, since if I know a non-trivial divisor of the integer, and I want to convince you that it is composite. I can just tell you that number and you can check yourself. To make this more concrete, if I gave you the number 1517 and asked you if it were prime or composite, you would have to do a lot of unpleasant arithmetic. But, if told you 1517 is 37 times 41, you'd be able to check this easily.
Now, it actually turns out that whether a number is prime composite can actually be checked quickly using something called the AKS algorithm . This result was a very big deal, proven by Manindra Agrawal and two other mathematicians in 2002 . I remember when this happened. When the result was announced, I was a high school student who was then at PROMYS, a summer math program at Boston University, and people were distributing and looking over copies of the preprint. The algorithm they used was straightforward, but proving that algorithm really did what was claimed required deeper mathematical results from the area known as sieve theory.
Let's try to make these notions of P and NP more mathematically rigorous. To do that, we need a rigorous notion of what it means to calculate quickly. We want the length of time it takes to run our algorithims to solve our problems to not grow very fast. When mathematicians want something that doesn't grow too quickly, they often look at polynomials (that is, functions like n^2, or n^3, or n^4 +10n +2, as opposed to say exponentials that look like 2^n or 3^n). So, we will define an algorithm to be quick if the amount of time it takes to run is bounded by a polynomial of the length of whatever we inputted. So ,for example, in our earlier case of looking at whether an integer is prime or composite, the length of the input would be the number of digits in the integer. Thus, Agrawal constructed an algorithm that ran would when given an integer always tell you if the integer was prime or composite. Agrawal showed that there is a constant K such that his algorithm terminates in at most at most Kn^12 steps, where n is the number of digits of of the number to be test.
Whether P = NP is one of the great unsolved problems of modern mathematics. P ?= NP is one the seven Clay Millenium Problems, each of which has a million dollar prize. Moreover, there are many practical applications. There are many practical problems which appear in some form to be in NP, but have no known quick algorithm to solve them. These include problems in protein folding, circuit design, and others areas.
Readers have likely also benefited more directly from practical issues related to this problem without even realizing it. I've discussed on this blog before the Diffie-Hellman algorithm. This is one example of many cryptographic systems that are used by modern computer networks, most often without users even realizing that they are being used. These all rest on certain problems being easy to solve if one has extra information, but very difficult otherwise. Thus, if P = NP, then all these algorithms will become insecure. This would be bad. Unfortunately, the converse does not follow: There is a common misconception that if P is not equal to NP, then modern encryption is actually safe. This doesn't follow. It turns out that claims that encryption works implies that P is not equal to NP, but the reverse doesn't follow. It is conceivable (although unlikely) that P and NP are distinct and encryption still collapses. But, figuring out whether P = NP would be a major step in understanding whether or not encryption is really safe.
Those worried about the encryption for their bank accounts can rest easy. Most experts in the field seem to think that P and NP are distinct. This means your encryption is secure. On the other hand, this also means that a lot of practical problems are genuinely tough. One can't have it both ways. Either one gets lots of helpful fast algorithms or one gets good encryption. Right now, it looks like one gets good encryption.
So, how close are we to actually answering if P = NP? This looks pretty far off right now. There are a few methods that look somewhat promising, but a lot of the best current results are results that essentially show that certain techniques cannot answer the question. So right now resolving the question looks pretty far off.
"P ?= NP" was and that I had completely failed to explain what I was talking about. They are correct. This entry is to remedy that problem.
First an analogy: Suppose you have a jigsaw puzzle. Assembling the puzzle correctly is difficult. But, if someone has the puzzle completed, one can generally tell at a glance that the puzzle is correct. (This isn't strictly true if you are dealing with someone like me who as a little kid would sometimes shove the pieces to fit in where they didn't belong. If one does this to sections that depict sky and clouds, it can be quite hard to tell that it is wrong.) But it seems that it is very difficult to tell how to assemble a puzzle. Moreover, it isn't even clear if one has all the pieces of the puzzle until one is nearly done with the puzzle. It can be a very frustrating experience to be nearly done with a puzzle and then realize that pieces are missing. What if there were a way to tell just from looking at the jumbled pieces in the box if one had the all pieces? Whether P is equal to NP is essentially asking if this is possible. The general consensus among computer scientists is that P is not equal to NP which means that puzzle-solvers are out of luck.
Let's break this down further. P is the set of types of puzzles that can be essentially solved quickly. So for example, "Is a given integer even or odd?" is a problem that lies in P. Given an integer, one can just look at the leading digit and see if it is even or odd. (I'm assuming that our integers are written in base 10). Similarly, the problem "given integers a and b, does a divide b?" is in P,;all one needs to do is divide a into b and see if there is a remainder. But not everything is necessarily in P. For example, the question, "is a given integer composite?" is not obviously in P, since checking requires successive search for divisors.
But, there is a larger class of problems, NP, which are problems which, if they have an answer of "yes," one can quickly convince someone else of the answer if one has the right information. In this context, "is an integer composite?" is in NP, since if I know a non-trivial divisor of the integer, and I want to convince you that it is composite. I can just tell you that number and you can check yourself. To make this more concrete, if I gave you the number 1517 and asked you if it were prime or composite, you would have to do a lot of unpleasant arithmetic. But, if told you 1517 is 37 times 41, you'd be able to check this easily.
Now, it actually turns out that whether a number is prime composite can actually be checked quickly using something called the AKS algorithm . This result was a very big deal, proven by Manindra Agrawal and two other mathematicians in 2002 . I remember when this happened. When the result was announced, I was a high school student who was then at PROMYS, a summer math program at Boston University, and people were distributing and looking over copies of the preprint. The algorithm they used was straightforward, but proving that algorithm really did what was claimed required deeper mathematical results from the area known as sieve theory.
Let's try to make these notions of P and NP more mathematically rigorous. To do that, we need a rigorous notion of what it means to calculate quickly. We want the length of time it takes to run our algorithims to solve our problems to not grow very fast. When mathematicians want something that doesn't grow too quickly, they often look at polynomials (that is, functions like n^2, or n^3, or n^4 +10n +2, as opposed to say exponentials that look like 2^n or 3^n). So, we will define an algorithm to be quick if the amount of time it takes to run is bounded by a polynomial of the length of whatever we inputted. So ,for example, in our earlier case of looking at whether an integer is prime or composite, the length of the input would be the number of digits in the integer. Thus, Agrawal constructed an algorithm that ran would when given an integer always tell you if the integer was prime or composite. Agrawal showed that there is a constant K such that his algorithm terminates in at most at most Kn^12 steps, where n is the number of digits of of the number to be test.
Whether P = NP is one of the great unsolved problems of modern mathematics. P ?= NP is one the seven Clay Millenium Problems, each of which has a million dollar prize. Moreover, there are many practical applications. There are many practical problems which appear in some form to be in NP, but have no known quick algorithm to solve them. These include problems in protein folding, circuit design, and others areas.
Readers have likely also benefited more directly from practical issues related to this problem without even realizing it. I've discussed on this blog before the Diffie-Hellman algorithm. This is one example of many cryptographic systems that are used by modern computer networks, most often without users even realizing that they are being used. These all rest on certain problems being easy to solve if one has extra information, but very difficult otherwise. Thus, if P = NP, then all these algorithms will become insecure. This would be bad. Unfortunately, the converse does not follow: There is a common misconception that if P is not equal to NP, then modern encryption is actually safe. This doesn't follow. It turns out that claims that encryption works implies that P is not equal to NP, but the reverse doesn't follow. It is conceivable (although unlikely) that P and NP are distinct and encryption still collapses. But, figuring out whether P = NP would be a major step in understanding whether or not encryption is really safe.
Those worried about the encryption for their bank accounts can rest easy. Most experts in the field seem to think that P and NP are distinct. This means your encryption is secure. On the other hand, this also means that a lot of practical problems are genuinely tough. One can't have it both ways. Either one gets lots of helpful fast algorithms or one gets good encryption. Right now, it looks like one gets good encryption.
So, how close are we to actually answering if P = NP? This looks pretty far off right now. There are a few methods that look somewhat promising, but a lot of the best current results are results that essentially show that certain techniques cannot answer the question. So right now resolving the question looks pretty far off.
Sunday, June 26, 2011
Gasarch P = NP Poll
A decade ago, Bill Gasarch conducted an informal poll asking computer scientists and mathematicians various questions related to whether or not P was equal to NP. He asked when people thought the problem would be resolved, which was it would be resolved, and what techniques they thought would be used. One thing that is striking about Gasarch's data is that a surprisingly large fraction of serious computer scientists seem to think that P = NP. Moreover, while Gasarch notes that some of those individuals explicitly said they were saying it for the sake of being contrary, a large fraction also were simply unwilling to guess which way it would be resolved.
Now, Gasarch is again conducting such a poll. I am noting this here, because he is accepting emails from not just computer scientists but individuals in general, although he wants people to note their academic background. Also, please note that he wants replies by email. Apparently some people have already failed to note this and have added them as comments to his announcement post.
My own opinion (which I will submit via email shortly), is that P != NP, and I'm about 95% confident in this regard. I assign low probability to the weirder possible results involving undecidability in ZFC. I have no idea when the problem will be resolved, and I have no idea what techniques will be used to resolve it, although the techniques used by both Mulmuley and Ryan Williams look interesting. Obviously, I'm not a computer scientist, so my opinions on these matters should be taken with a large dose of salt.
Gasarch's poll also has an open-ended question allowing one to pontificate on related issues. Unfortunately, I really don't have any strong opinion on any related issues other than something like "derandomization is nice, yay?" The obvious related question of whether P = BPP seems tough. A lot of people are convinced that this is the case, and there's been a lot of success in the last few years with derandomizing algorithms, but my impression is that there's very little in the way of general techniques of how to do this systematically.
I'm also curious what readers of this blog thing, so feel free to leave your speculations in the comments.
Now, Gasarch is again conducting such a poll. I am noting this here, because he is accepting emails from not just computer scientists but individuals in general, although he wants people to note their academic background. Also, please note that he wants replies by email. Apparently some people have already failed to note this and have added them as comments to his announcement post.
My own opinion (which I will submit via email shortly), is that P != NP, and I'm about 95% confident in this regard. I assign low probability to the weirder possible results involving undecidability in ZFC. I have no idea when the problem will be resolved, and I have no idea what techniques will be used to resolve it, although the techniques used by both Mulmuley and Ryan Williams look interesting. Obviously, I'm not a computer scientist, so my opinions on these matters should be taken with a large dose of salt.
Gasarch's poll also has an open-ended question allowing one to pontificate on related issues. Unfortunately, I really don't have any strong opinion on any related issues other than something like "derandomization is nice, yay?" The obvious related question of whether P = BPP seems tough. A lot of people are convinced that this is the case, and there's been a lot of success in the last few years with derandomizing algorithms, but my impression is that there's very little in the way of general techniques of how to do this systematically.
I'm also curious what readers of this blog thing, so feel free to leave your speculations in the comments.
Monday, June 20, 2011
Planar Divisibility Graphs and The Bible
I've talked about graph theory here before in the context of Ramsey theory.
However, there are many other interesting graph theory problems.
A graph is said to be planar if one can draw it on a plane with none of the edges intersecting. So for example, K3, the graph formed by three vertices all of which connect to each other is planar, but the similar graph K5 formed by five vertices all of which connect is not planar.
We can also change our notion of graph by allowing our edges to have directions, and represent them with arrows rather than straight lines. Thus for example, if one wanted to use a graph to represent who knows the name of whom with a bunch of people, using a directed graph would be quite natural.
Over the last few days I have been thinking about divisibility graphs of sets. These graphs arise when one takes some set of positive integers and assigns each to a vertex then draws the corresponding arrows when one integer divides another. (So for example, if our set was was {1,2,4} then 1 would have arrows going to 2 and 4 and 2 would have an arrow going to 4). For convenience, I am ignoring the arrows that vertices would have going to themselves.
Now, assume one has a set of positive integers A and we know that corresponding divisibility graph is planar. What can we say about how large the set is. That is, if we let A(x) be the number of elements in A which are at most x, how fast does A(x) grow? It is not difficult to see that one can get A(x) to grow at least about as fast as x/log x. One does this by taking A to be the set of prime numbers. The resulting graph is certainly planar since it has no edges at all. Then the prime number theorem does the rest. With a small amount of tweaking, one can get this to grow at about 2x/log x since one can include all the numbers of the form 2p and still get a planar graph. I suspect that the actual best possible growth is on the order of x/log x but I'm not sure. One possible approach to making a large planar divisibility graph is to use the greedy algorithm. That is, throw 1 into the set and then go by induction on each integer, throwing in the next integer if it still allows a planar graph. If one call this set G, then the first number not in G is 18. It seems at first that G grows quickly, and G includes every prime number. But most large integers are in fact not in G, a result of the fact that most large integers have a lot of prime factors. For example, every multiple of 6 other than 6 and 12 is not in G.
Now, you may be thinking, "Josh, this is an interesting math problem, but the title mentioned the Bible. What does that have to do with anything?" The truth is that the connection is tenuous. The problem about planar divisibility graphs occurred to me when I was tutoring a professor's young kid in graph theory, and we discussed divisibility graphs. The professor's family is Orthodox, and so another graph we talked was to take different Biblical figures and make a graph representing who had met whom. The major graph had three large components, one corresponding to the patriarchal time period (with Abraham, Issac and Jacob as the most connected points), one to the time around the Exodus (with Moses at the center), and one at the early monarchy, with David, Samuel and Solomon as the main points. However, an issue came up. My young student wanted to add Eli, the high priest during most of the of Samuel to the graph. This raised an issue which neither he nor I knew the answer: Did Eli ever encounter David? The text does not mention such an event, but the chronology seems tentatively to allow such a meeting. I'm also unaware of any midrashim claiming that they met. I'm mentioning this here therefore for two reasons: One can any more knowledgeable readers point me to anything in the text itself which deals with this, or can any of my more midrashically inclined readers point me to any midrashim that address whether they met?
However, there are many other interesting graph theory problems.
A graph is said to be planar if one can draw it on a plane with none of the edges intersecting. So for example, K3, the graph formed by three vertices all of which connect to each other is planar, but the similar graph K5 formed by five vertices all of which connect is not planar.
We can also change our notion of graph by allowing our edges to have directions, and represent them with arrows rather than straight lines. Thus for example, if one wanted to use a graph to represent who knows the name of whom with a bunch of people, using a directed graph would be quite natural.
Over the last few days I have been thinking about divisibility graphs of sets. These graphs arise when one takes some set of positive integers and assigns each to a vertex then draws the corresponding arrows when one integer divides another. (So for example, if our set was was {1,2,4} then 1 would have arrows going to 2 and 4 and 2 would have an arrow going to 4). For convenience, I am ignoring the arrows that vertices would have going to themselves.
Now, assume one has a set of positive integers A and we know that corresponding divisibility graph is planar. What can we say about how large the set is. That is, if we let A(x) be the number of elements in A which are at most x, how fast does A(x) grow? It is not difficult to see that one can get A(x) to grow at least about as fast as x/log x. One does this by taking A to be the set of prime numbers. The resulting graph is certainly planar since it has no edges at all. Then the prime number theorem does the rest. With a small amount of tweaking, one can get this to grow at about 2x/log x since one can include all the numbers of the form 2p and still get a planar graph. I suspect that the actual best possible growth is on the order of x/log x but I'm not sure. One possible approach to making a large planar divisibility graph is to use the greedy algorithm. That is, throw 1 into the set and then go by induction on each integer, throwing in the next integer if it still allows a planar graph. If one call this set G, then the first number not in G is 18. It seems at first that G grows quickly, and G includes every prime number. But most large integers are in fact not in G, a result of the fact that most large integers have a lot of prime factors. For example, every multiple of 6 other than 6 and 12 is not in G.
Now, you may be thinking, "Josh, this is an interesting math problem, but the title mentioned the Bible. What does that have to do with anything?" The truth is that the connection is tenuous. The problem about planar divisibility graphs occurred to me when I was tutoring a professor's young kid in graph theory, and we discussed divisibility graphs. The professor's family is Orthodox, and so another graph we talked was to take different Biblical figures and make a graph representing who had met whom. The major graph had three large components, one corresponding to the patriarchal time period (with Abraham, Issac and Jacob as the most connected points), one to the time around the Exodus (with Moses at the center), and one at the early monarchy, with David, Samuel and Solomon as the main points. However, an issue came up. My young student wanted to add Eli, the high priest during most of the of Samuel to the graph. This raised an issue which neither he nor I knew the answer: Did Eli ever encounter David? The text does not mention such an event, but the chronology seems tentatively to allow such a meeting. I'm also unaware of any midrashim claiming that they met. I'm mentioning this here therefore for two reasons: One can any more knowledgeable readers point me to anything in the text itself which deals with this, or can any of my more midrashically inclined readers point me to any midrashim that address whether they met?
Thursday, June 16, 2011
Abusing Statistics
A friend writing under a pseudonym has a new blog about the use and abuse of statistics in the media. He's a good writer. Since he came to statistics (and the mathy end of everything) somewhat late compared to most math and science bloggers, I expect that his take will be quite interesting. He will likely also do a good job explaining some of the relevant ideas to less mathematical people. The latest entry is on how not to conduct surveys. The entry is worth reading.
Monday, June 6, 2011
Dungeons, Dragons and Halacha
In an earlier entry I discussed whether under halachah (Orthodox Jewish law) it would be acceptable to make a horcrux or become a lich if either were possible in real life. That entry was largely an excuse for bad wordplay related to the word "phylactery" which has a variety of meanings. A phylactery is in the most general sense an object which contains someting of religious or ritual significance. In the most common context, the word is used in the plural- "phylacteries" as an English translation of tefilin, the small boxes worn by some Jews at morning prayers. Another use of term is in Dungeons and Dragons, where the term is used to describe the object that a lich, a type of undead wizard, uses to store their soul.
However, I recently came across yet another meaning of this term in a Dungeons and Dragons context. There is a spell, described in the D&D book "Player's Guide to Faerun" called "Spell Phylactery" which allows one to store a spell on a scroll which "must be bound to your arm or forehead (usually rolled tightly or placed in a small box for this purpose)". This form seems more directly inspired by the phylacteries of the Jewish tradition. Unfortunately, even if D&D magic were real, it would not be halachically acceptable to make a three-way phylactery since the Spell Phylactery spell can only be cast by a worshipper of the goddess Mystra, which would be not allowed under halacha. Too bad. I really wanted phylacteries that functioned as both a phylactery and as a spell phylactery.
However, I recently came across yet another meaning of this term in a Dungeons and Dragons context. There is a spell, described in the D&D book "Player's Guide to Faerun" called "Spell Phylactery" which allows one to store a spell on a scroll which "must be bound to your arm or forehead (usually rolled tightly or placed in a small box for this purpose)". This form seems more directly inspired by the phylacteries of the Jewish tradition. Unfortunately, even if D&D magic were real, it would not be halachically acceptable to make a three-way phylactery since the Spell Phylactery spell can only be cast by a worshipper of the goddess Mystra, which would be not allowed under halacha. Too bad. I really wanted phylacteries that functioned as both a phylactery and as a spell phylactery.
Subscribe to:
Posts (Atom)
