This is a lovely little story about pay phones on Whidbey Island. Warning: those who spent too much time with phone systems in their youth may feel inexplicable nostalgia.
So there’s a working set of plans for the “Liberator.” It’s a working firearm you can print on a 3d printer. You can no longer get the files from the authors, whose site states: “DEFCAD files are being removed from public access at the request of the US Department of Defense Trade Controls.
Until further notice, the United States government claims control of the information.” Cue Streisand Effect.
My understanding is that the censorship order was issued under the ITARs, the “International Traffic in Arms Regulations.” Cory Doctorow has said “Impact litigation — where good precedents overturn bad rules — is greatly assisted by good facts and good defendants. I would much rather the Internet-as-library question be ruled on in a less emotionally overheated realm than DIY guns.” I think that’s reasonable, but recall that Shaw claimed that all progress depends on the unreasonable man.
Doctorow also refers to Bernstein, who did good work, but his lawsuit was the last nail in ITARs applying to crypto, not the first. (ITARs still do apply to crypto, but in ways that allow both open source and commercial software to ship strong crypto, which wasn’t the case in the 90s.) Me, I see lots of evidence that gun control doesn’t work any better than alcohol control or marijuana control. And I think that the regulatory response by the DoD is silly. (One can argue that the law gives them no choice, but I don’t believe that to be the case.)
So the right step was demonstrated for crypto nearly 20 years ago by Phil Karn. He filed a pair of “Commodity Jurisdiction Requests.” One for Applied Cryptography, a book, and one for a floppy disk containing the source code.
The State Department ruled that even though the book itself is “in the public domain” and hence outside their jurisdiction, a floppy disk containing the exact same source code as printed in the book is a “munition” requiring a license to export. It’s old news that the US Government believes only Americans (and maybe a few Canadians) can write C code, but now they have apparently decided that foreigners can’t type either!
In the past three years I have taken my case to all three branches of the federal government. Here is the full case history in the Executive and Judicial branches, including all my correspondence with the US State Department, the Bureau of Export Administration (BXA) in the Commerce Department, the US District Court for the District of Columbia, and the Court of Appeals for the DC Circuit.
I believe the analogy is obvious. The DefCad files are 2mb zipped, and the STL files can be opened with a variety of software. Unfortunately, STL looks to be a binary format, and it’s not clear to me after a few minutes of searching if there’s a trivially printed text format. But that’s a very low hurdle.
As Doctorow implied, reasonableness on all sides would be nice to have. But at home printing isn’t going to go away, and censorship orders are not a productive step forward.
[Previously here: “What Should a Printer Print?“]
In CONGRESS, July 4, 1776
The unanimous Declaration of the thirteen united States of America,
When in the Course of human events, it becomes necessary for one people to dissolve the political bands which have connected them with another, and to assume among the powers of the earth, the separate and equal station to which the Laws of Nature and of Nature’s God entitle them, a decent respect to the opinions of mankind requires that they should declare the causes which impel them to the separation.
We hold these truths to be self-evident, that all men are created equal, that they are endowed by their Creator with certain unalienable Rights, that among these are Life, Liberty and the pursuit of Happiness. –That to secure these rights, Governments are instituted among Men, deriving their just powers from the consent of the governed, –That whenever any Form of Government becomes destructive of these ends, it is the Right of the People to alter or to abolish it, and to institute new Government, laying its foundation on such principles and organizing its powers in such form, as to them shall seem most likely to effect their Safety and Happiness. Prudence, indeed, will dictate that Governments long established should not be changed for light and transient causes; and accordingly all experience hath shewn, that mankind are more disposed to suffer, while evils are sufferable, than to right themselves by abolishing the forms to which they are accustomed. But when a long train of abuses and usurpations, pursuing invariably the same Object evinces a design to reduce them under absolute Despotism, it is their right, it is their duty, to throw off such Government, and to provide new Guards for their future security. —Such has been the patient sufferance of these Colonies; and such is now the necessity which constrains them to alter their former Systems of Government. The history of the present King of Great Britain [George III] is a history of repeated injuries and usurpations, all having in direct object the establishment of an absolute Tyranny over these States. To prove this, let Facts be submitted to a candid world.
He has refused his Assent to Laws, the most wholesome and necessary for the public good.
He has forbidden his Governors to pass Laws of immediate and pressing importance, unless suspended in their operation till his Assent should be obtained; and when so suspended, he has utterly neglected to attend to them.
He has refused to pass other Laws for the accommodation of large districts of people, unless those people would relinquish the right of Representation in the Legislature, a right inestimable to them and formidable to tyrants only.
He has called together legislative bodies at places unusual, uncomfortable, and distant from the depository of their public Records, for the sole purpose of fatiguing them into compliance with his measures.
He has dissolved Representative Houses repeatedly, for opposing with manly firmness his invasions on the rights of the people.
He has refused for a long time, after such dissolutions, to cause others to be elected; whereby the Legislative powers, incapable of Annihilation, have returned to the People at large for their exercise; the State remaining in the mean time exposed to all the dangers of invasion from without, and convulsions within.
He has endeavoured to prevent the population of these States; for that purpose obstructing the Laws for Naturalization of Foreigners; refusing to pass others to encourage their migrations hither, and raising the conditions of new Appropriations of Lands.
He has obstructed the Administration of Justice, by refusing his Assent to Laws for establishing Judiciary powers.
He has made Judges dependent on his Will alone, for the tenure of their offices, and the amount and payment of their salaries.
He has erected a multitude of New Offices, and sent hither swarms of Officers to harass our people, and eat out their substance.
He has kept among us, in times of peace, Standing Armies without the consent of our legislatures.
He has affected to render the Military independent of and superior to the Civil power.
He has combined with others to subject us to a jurisdiction foreign to our constitution and unacknowledged by our laws; giving his Assent to their Acts of pretended Legislation:
For Quartering large bodies of armed troops among us:
For protecting them, by a mock Trial, from punishment for any Murders which they should commit on the Inhabitants of these States:
For cutting off our Trade with all parts of the world:
For imposing Taxes on us without our Consent:
For depriving us, in many cases, of the benefits of Trial by Jury:
For transporting us beyond Seas to be tried for pretended offences:
For abolishing the free System of English Laws in a neighbouring Province, establishing therein an Arbitrary government, and enlarging its Boundaries so as to render it at once an example and fit instrument for introducing the same absolute rule into these Colonies:
For taking away our Charters, abolishing our most valuable Laws, and altering fundamentally the Forms of our Governments:
For suspending our own Legislatures, and declaring themselves invested with power to legislate for us in all cases whatsoever.
He has abdicated Government here, by declaring us out of his Protection and waging War against us.
He has plundered our seas, ravaged our Coasts, burnt our towns, and destroyed the lives of our people.
He is at this time transporting large Armies of foreign Mercenaries to compleat the works of death, desolation and tyranny, already begun with circumstances of Cruelty and perfidy scarcely paralleled in the most barbarous ages, and totally unworthy the Head of a civilized nation.
He has constrained our fellow Citizens taken Captive on the high Seas to bear Arms against their Country, to become the executioners of their friends and Brethren, or to fall themselves by their Hands.
He has excited domestic insurrections amongst us, and has endeavoured to bring on the inhabitants of our frontiers, the merciless Indian Savages, whose known rule of warfare, is an undistinguished destruction of all ages, sexes and conditions.
In every stage of these Oppressions We have Petitioned for Redress in the most humble terms: Our repeated Petitions have been answered only by repeated injury. A Prince whose character is thus marked by every act which may define a Tyrant, is unfit to be the ruler of a free people.
Nor have We been wanting in attentions to our British brethren. We have warned them from time to time of attempts by their legislature to extend an unwarrantable jurisdiction over us. We have reminded them of the circumstances of our emigration and settlement here. We have appealed to their native justice and magnanimity, and we have conjured them by the ties of our common kindred to disavow these usurpations, which, would inevitably interrupt our connections and correspondence. They too have been deaf to the voice of justice and of consanguinity. We must, therefore, acquiesce in the necessity, which denounces our Separation, and hold them, as we hold the rest of mankind, Enemies in War, in Peace Friends.
We, therefore, the Representatives of the united States of America, in General Congress, Assembled, appealing to the Supreme Judge of the world for the rectitude of our intentions, do, in the Name, and by the Authority of the good People of these Colonies, solemnly publish and declare, That these United Colonies are, and of Right ought to be Free and Independent States; that they are Absolved from all Allegiance to the British Crown, and that all political connection between them and the State of Great Britain, is and ought to be totally dissolved; and that as Free and Independent States, they have full Power to levy War, conclude Peace, contract Alliances, establish Commerce, and to do all other Acts and Things which Independent States may of right do. And for the support of this Declaration, with a firm reliance on the protection of divine Providence, we mutually pledge to each other our Lives, our Fortunes and our sacred Honor.
The signers of the Declaration represented the new states as follows:
Josiah Bartlett, William Whipple, Matthew Thornton
John Hancock, Samual Adams, John Adams, Robert Treat Paine, Elbridge Gerry
Stephen Hopkins, William Ellery
Roger Sherman, Samuel Huntington, William Williams, Oliver Wolcott
William Floyd, Philip Livingston, Francis Lewis, Lewis Morris
Richard Stockton, John Witherspoon, Francis Hopkinson, John Hart, Abraham Clark
Robert Morris, Benjamin Rush, Benjamin Franklin, John Morton, George Clymer, James Smith, George Taylor, James Wilson, George Ross
Caesar Rodney, George Read, Thomas McKean
Samuel Chase, William Paca, Thomas Stone, Charles Carroll of Carrollton
George Wythe, Richard Henry Lee, Thomas Jefferson, Benjamin Harrison, Thomas Nelson, Jr., Francis Lightfoot Lee, Carter Braxton
William Hooper, Joseph Hewes, John Penn
Edward Rutledge, Thomas Heyward, Jr., Thomas Lynch, Jr., Arthur Middleton
Button Gwinnett, Lyman Hall, George Walton
Image: Washington’s copy of the Declaration of Independence, from the Library of Congress.
Emergent Chaos has a long tradition of posting the American Declaration of Independence here to celebrate the holiday. It’s a good document in many ways. It’s still moving, more than two centuries after it was written. It’s clearly written, and many people can learn from its structured approach to presenting a case. And last but not least, it’s a document celebrating that we all are created equal, with certain inalienable rights. That none of us is a king or a serf by accident of birth, with special rights by those circumstances.
And so today I’d like to talk a little about the extraordinary events in the Arab world over the last six months. When Muhammad Al Bouazizi set himself on fire, it was unlikely that he knew that his actions would set in motion events including the downfall of the Tunisian and Egyptian governments, a civil war in Lybia, and a revolt against King Assad in Syria. (Yes, I know that’s not his official title, but Presidents don’t inherit the title from their fathers.)
It’s easy to assert that these are American values rising up in the Arab world, or that Twitter or Facebook are somehow central. I don’t want to be so facile.
What is happening is that the Egyptians are struggling to force a new reality of law onto their current military government, with a release of protestors, and end to torture of prisoners and especially the sexual abuse of women prisoners. They are working to ensure that they have free and fair elections as soon as possible.
The Libyans are engaged in an all-out civil war. Colonel Khadafi, accused kleptocrat and now wanted war criminal, has lots of money, and repeated NATO attempts to kill him have failed. (I think these are legitimate attempts-he’s a military officer, and killing him as part of a military operation would be a legitimate act of war. If he had a reasonable separation and a military commander, then it would be assassination.)
The Syrians are engaged in an all-out revolt against their King, with little notice or support from the wider world. The same situation applied in Yemen, except their King claimed that title, and he’s now on life support in Saudi Arabia. As an aside, when the only place that will take you in doesn’t let women drive, you’re on the wrong side of history.
So for all this chaos, I’m optimistic for the Arab peoples. Their struggles to build socieities will be hard. They will have detours. Their first attempts to build societies after throwing off their Kings will be troublesome. Much like after we threw out the British, we had our Articles of Confederation, we had our whiskey and Shay’s rebellions, and we even had a civil war over issues that our founding fathers couldn’t hammer out themselves.
So I don’t expect what the Arab states are going through will be simple or easy. But I do know that tens of millions of people now have more say in their future than they did, and that’s a fine thing to celebrate this Independence Day.
There’s an excellent column in the old liberal tradition of celebrating liberty in this week’s New Yorker. It’s Memorials by Adam Goptnick, and includes a quote from John Stuart Mill at his rhetorical peak.
The people of Tunisia have long been living under an oppressive dictator who’s an ally of the US in our ‘war on terror.’ Yesterday, after substantial loss of life, street protests drove the dictator to abdicate. There’s lots of silly technologists claiming it was twitter. A slightly more nuanced comment is in “Sans URL” Others, particularly Jillian York, said “Not Twitter, Not WikiLeaks: A Human Revolution.” Ethan Zuckerman had insightful commentary including “What if Tunisia had a revolution, but nobody watched?” and “A reflection on Tunisia.”
That conversation is interesting and in full swing. What I want to ask about is the aftermath and the challenges that Tunisia faces. After 24 years of oppression, it’s going to be hard to build the political structures needed to create a legitimate and accepted government.
The American revolution came after years of discussion of British abuses of power. American perceptions of abuses of power like the Stamp Act combined with slow communication to the King and fast local communication to create a local political class that could assemble in a continental congress. Even so, after the American revolution, we had one entirely failed government under the Articles of Confederation, which was replaced with our current Constitution. But that was followed by the whiskey rebellion.
I bring this up because it’s easy to focus on the mechanics of government while forgetting about the soil in which it grows. Perhaps the digital world, with its ability to connect Tunisians to people living in places where we’ve worked these things out, will help. (For those foreigners who speak Arabic, or those Tunisians who speak other languages.) I’m not terribly optimistic in light of the shootings in Arizona and how quickly the online discourse devolved into “why this tragedy proves I’m right.” I’m also not optimistic given our poor understanding of our history.
I am, however, hopeful that the people of Tunisia will manage to take a collective break from the violence for long enough to work out a Tunisian approach to democracy. What would that look like? Would technology play a role?
It’s MLK Day.
Here’s a pdf of the speech.
Or watch it online:
There’s been a lot of discussion about the paper written by mathematician Vinay Deolalikar on this interesting problem.
The P!=NP problem is so interesting that there’s a million-dollar prize for solving it. It might even be interesting because there’s a million-dollar prize for solving it. It might also have some applicability to computer science and even cryptography. The August 11 edition of Deolalikar’s paper can be found here.
Because this is an interesting problem, there’s a lot of pressure on domain experts and pseudo-experts to comment. I classify myself as more pseudo-expert than expert, so color your filters accordingly.
Among the real experts, my favorite is Scott Aaronson, who is an expert in complexity theory and quantum information science. If you aren’t completely clear on the whole thing, his essay, “P vs. NP for Dummies” is a good place to start.
His essay, “Putting my money where my mouth isn’t,” is a marvelous snap response. In it, he says that he’s willing to contribute his on $200,000 to the million-dollar prize, should this proof be right. He gives some great reasons for his own snap commentary and his own decision not to cancel his vacation to look at the paper.
Aaronson also points to his own essay from 2008, “Ten Signs a Claimed Mathematical Breakthrough is Wrong,” which you should be reading before you read anything about Deolalikar’s paper. It’s not about Deolalikar, it’s about the general issue of breakthrough papers of any sort.
But getting back to this particular paper, there’s a lot of skepticism, and a good summary of the skepticism comes from Terence Tao.
I’ll add in my own raised eyebrow along with my own general discussion of P!=NP. I have three points:
- P!=NP really isn’t interesting.
- Most comments about the whole P vs. NP don’t understand the ramifications of it, especially when dealing with practical disciplines like computer science and cryptography.
- The reason I have a raised eyebrow centers around those two above.
So here we go.
P!=NP really isn’t interesting. What would be interesting would be if someone proved that P=NP. We all expect that P!=NP, we act as if it’s true. On the one hand, that means I’m far more likely to believe Deolalikar because he’s proving that which we expect to be true. On the other hand, that means it’s harder evaluate his proof because it is proving something we all think is true.
Understanding P vs. NP. Conventional wisdom about P and NP often includes thoughts such as, “The implications of this [P=NP] on applications such as cryptography, and on the general philosophical question of whether human creativity can be automated, would be profound.” I disagree. I think that if it turns out to the shock of everyone that P=NP, it will be a yawn.
Let’s suppose that P=NP, which means that a large class of problems have solutions in polynomial time. Great. That doesn’t mean they’re easy to solve. It doesn’t mean that the solutions are even useful.
Here’s an example. A few years ago, we got a polynomial time primality test algorithm, the AKS test (named for its authors, Manindra Agrawal, Neeraj Kayal, and Nitin Saxena). Originally, it was an x12 algorithm, and everyone needing primality testing ignored it, because that’s too slow. It’s been improved to x6, which is still too slow. It’s polynomial, but that doesn’t matter.
In practical terms for cryptography, let’s suppose you want to generate a 2048-bit RSA key. For that, you need two 1024-bit primes. Right now, the tests that we use are “probabilistic.” I put quotes around it because while there’s no guarantee that the number that passes the probabilistic test is actually prime, no one has ever (knowingly) found a number that passed the probabilistic test and was not actually prime. In fact, if you found such a number, it would be a result worthy of publication. Thus, the risk of the inexact test is very low. But the cost of the exact test is 10246 which is a very large number, 1,152,921,504,606,846,976, and we can’t really afford that.
Thus, for this function that’s useful for crypto, primality testing, we know that there is a P solution, x6 is too large a P. The fact that it is P turns out to be uninteresting.
For the purposes of cryptography, even x3 is probably not good enough. Some time ago, I harumphed about quantum computers doing factoring, and much of my harumphing boils down this observation — that even a low power polynomial like a cubic may leave the advantage to the code-maker over the code-breaker.
This is why I think that if P=NP, it could still be a yawn. If you find a polynomial solution with an exponent of somewhere in the 3-10 range, they are so hard so fast that the fact that the solution is polynomial is a merely a factoid. It seems a good bet that if there were a quadratic-scale algorithm for factoring, we’d know it.
This is a subtle point, so I’ll make it one more time. If P=NP, it’s only interesting if the polynomial is of low order. Polynomial-time problems can easily be intractable.
If it turns out that a bunch of cryptographic problems are polynomial, but order x6 or more, then the cryptographers aren’t going to lose a lot of sleep. In fact, they’ll have a good reason to get everyone to upgrade all their software, and that will be pretty much the end of it.
On the flip side of this, most NP-complete problems we know about are not as hard as we’re led to believe. The most famous NP-complete is the Traveling Salesman Problem. While it is indeed very hard to come up with the shortest solution for arbitrary problems, it’s actually very easy to come up with acceptable solutions for reasonable problems. Heck, it’s not like actual traveling salesmen have lots of problems covering their routes. There is even a nice web page that computes routes on Google Maps. I think a good way to put this in perspective with the P vs. NP problem is to note that there is a prize for solving a 100,000 city problem, and that prize is $100.
Most of the genuine hard problems we have are only hard to solve on edge conditions. There are many attempts to create cryptosystems out of real NP-complete problems, and their track record is pitiful. We really don’t have any of them. I say “really” because we have one — lattice cryptography — and it still has issues. It’s slow, big, and complicated with intellectual property. Worse, some forms of lattice cryptography have had problems similar to the Traveling Salesman Problem. The GGH cryptosystem has the flaw that all ciphertexts leak information about the plaintext. Oops.
The bottom line here is that many problems that we know to be hard are easy in most cases and that “easy” problems might still be hard enough that they’re useful for protecting secrets. Whether P=NP or P!=NP is something that is interesting to mathematicians and philosophers far more than to scientists and engineers.
Raised eyebrow department. Now I get to why I’m so far skeptical. The quote that I gave above about what it would mean if P=NP comes from Deolalikar’s paper. Perhaps naïvely, I expect an expert on complexity theory to go beyond the usual science-reporting ooo-ahhs. I expect a complexity theorist to understand that complexity is complex, or at least subtle. I’m not a complexity theorist, I’m a mere complexity practitioner and I understand that complexity is hard to understand.
However, he’s right. If P=NP, it would be a deep discovery and have philosophical import. However, however, he’s proved the opposite, and so discussion about what it would mean if his proof were out of phase with what it actually proves seems weird.
Fine, fine. Everyone’s entitled to their soapbox, particularly when they do something significant. But reading through the proof there’s something missing. In brief, his proof has to prove that something that everyone thinks is hard is in fact actually hard. Ironically, this is harder than proving that it’s actually easy (which is again the proof of the opposite thing). Part of proving that something is hard ought to include showing that a related problem is easy.
In the P vs. NP world he’s chosen, he is showing that 3SAT is hard. 3SAT, to oversimplify, looks at the combinations of three boolean operations, such as A or B and C. 2SAT (combinations of two boolean operations) is known not to be hard. Had Deolalikar shown that 3SAT is hard and 2SAT is easy, I think we’d all be wowed. With only half of that, we’re left hanging and scratching our heads. Since we expect 3SAT to be hard, there needs to be some contrast against a related known easy problem for contrast. Without that contrast, it’s very hard to value the proof.
Worse, if one were to take his proof mechanism and apply it to 2SAT and come up with a conclusion that 2SAT is also hard, then there’s a huge hole in the proof. If I were analyzing the proof, I would in fact start by seeing how it applies to a few known-P problems. If it proves they are NP, we have a problem.
To sum up, I bet the proof doesn’t hold up because it only addresses the wheat, not the chaff. Any prover of P!=NP has to deal with the problem that we expect that to be true and that it’s hard to prove that something we think is hard actually is hard. Disproving it is easier in the sense that if you come up with an easy solution to something everyone thinks is hard, it is — um, well — hard to argue with that. Without some contrast, any proof of P!=NP looks on its surface as if you’re saying, “Hey everyone, you know that problem no one can easily solve? I can’t easily solve it, either!” That lacks intellectual force.
Nonetheless, maybe he has it. Maybe in a few months we’ll all be wowed, once it sinks in. Heck, maybe he doesn’t have it this summer, but next summer a revised proof will have us all cheering. Only time will tell. But right now, it’s interesting but unconvincing.
My personal bet, which I have no proof for, is that P!=NP is true but unprovable. I’m holding out for the proof that it’s unprovable.