(no subject)
Sep. 19th, 2003 12:46 am![[personal profile]](https://www.dreamwidth.org/img/silk/identity/user.png){kind=small}
zana16As requested, behind the cut-tag, my response paper to last week's Dialogues in Mathematics lecture.
Janaki Spickard-Keeler
Math 200
September 18, 2003
Response: P=NP?
Upon hearing the lecture, my thought process went in two different directions. I am a Government major and a Math minor, so there is always this dichotomy in me: half of me looks for the human story and the other half is intrigued by the mathematics. And as an author, I immediately started to form a story about a second-tier mathematician who discovers an easy algorithm for the solution of an NP-complete problem. If I understand this right, then all NP-complete problems, or hard problems as I prefer to think of them, can be done easily and so hacking into internet commerce is simple. But this mathematician isn’t so much an Andrew Wiles type interested in pure mathematics: he sees a criminal opportunity. He’s intelligent enough not to grind internet commerce to a halt and waste his access to all things saleable. A million dollars is pennies next to the money he can use on other peoples’ credit cards. But he knows he can’t rip off huge amounts from each source, or else the credit companies will see danger, so he spreads it out. In an age of accounting fraud, he can get away with bleeding off credit from various large companies and pinning the blame on overpaid CEOs and dishonest accountants. I got this far in my story before realizing I had 200 pages of Marx to read, and he was going to argue about the evils of money and selling oneself and one’s labor.
Deciding that this fictionalized account of what I’d be sorely tempted to do were I to prove that P=NP was not quite enough for this response paper, I checked out the Clay Millennium Problems webpage. I checked out the other problems, found most of them thoroughly incomprehensible, but I was used to this after only 30 pages of Marx’s version of history. I latched onto the first comprehensible link, http://www.claymath.org//Popular_Lectures/Minesweeper/ . As a college student who concentrates mostly on political and social theory, I have perfected the art of procrastination. While Minesweeper does not attain the levels of procrastinational enjoyment that Snood or Spider Solitaire does, it is nevertheless a very efficient timewaster that uses just enough of one’s brain that one cannot concentrate fully on the Plato-on-tape one is using to justify the procrastination. Well, it turns out that Minesweeper is NP-complete! “Kaye proves that Minesweeper is equivalent to SAT, in the following sense. The SAT problem for a given Boolean circuit can be 'encoded' as a Minesweeper Consistency Problem for some position in the game, using a code procedure that runs in polynomial time. Therefore, if you could solve the Minesweeper Consistency Problem in polynomial time, you would have solved the SAT problem for that circuit in polynomial time.” This makes the prospect of actually studying the P=NP? problem much less intimidating. I could play Minesweeper and call it research! If I found an “easy” algorithm for Minesweeper, I’d be in the ethical dilemma my imaginary second-tier mathematician created for himself. Curse my sense of morality. And curse Marx for convincing me that money really won’t make me happy or fulfilled.
Janaki Spickard-Keeler
Math 200
September 18, 2003
Response: P=NP?
Upon hearing the lecture, my thought process went in two different directions. I am a Government major and a Math minor, so there is always this dichotomy in me: half of me looks for the human story and the other half is intrigued by the mathematics. And as an author, I immediately started to form a story about a second-tier mathematician who discovers an easy algorithm for the solution of an NP-complete problem. If I understand this right, then all NP-complete problems, or hard problems as I prefer to think of them, can be done easily and so hacking into internet commerce is simple. But this mathematician isn’t so much an Andrew Wiles type interested in pure mathematics: he sees a criminal opportunity. He’s intelligent enough not to grind internet commerce to a halt and waste his access to all things saleable. A million dollars is pennies next to the money he can use on other peoples’ credit cards. But he knows he can’t rip off huge amounts from each source, or else the credit companies will see danger, so he spreads it out. In an age of accounting fraud, he can get away with bleeding off credit from various large companies and pinning the blame on overpaid CEOs and dishonest accountants. I got this far in my story before realizing I had 200 pages of Marx to read, and he was going to argue about the evils of money and selling oneself and one’s labor.
Deciding that this fictionalized account of what I’d be sorely tempted to do were I to prove that P=NP was not quite enough for this response paper, I checked out the Clay Millennium Problems webpage. I checked out the other problems, found most of them thoroughly incomprehensible, but I was used to this after only 30 pages of Marx’s version of history. I latched onto the first comprehensible link, http://www.claymath.org//Popular_Lectures/Minesweeper/ . As a college student who concentrates mostly on political and social theory, I have perfected the art of procrastination. While Minesweeper does not attain the levels of procrastinational enjoyment that Snood or Spider Solitaire does, it is nevertheless a very efficient timewaster that uses just enough of one’s brain that one cannot concentrate fully on the Plato-on-tape one is using to justify the procrastination. Well, it turns out that Minesweeper is NP-complete! “Kaye proves that Minesweeper is equivalent to SAT, in the following sense. The SAT problem for a given Boolean circuit can be 'encoded' as a Minesweeper Consistency Problem for some position in the game, using a code procedure that runs in polynomial time. Therefore, if you could solve the Minesweeper Consistency Problem in polynomial time, you would have solved the SAT problem for that circuit in polynomial time.” This makes the prospect of actually studying the P=NP? problem much less intimidating. I could play Minesweeper and call it research! If I found an “easy” algorithm for Minesweeper, I’d be in the ethical dilemma my imaginary second-tier mathematician created for himself. Curse my sense of morality. And curse Marx for convincing me that money really won’t make me happy or fulfilled.