The Web We Have to Save

Hossein Derakhshan was recently released from jail in Iran. He’s written a long and thoughtful article “The Web We Have to Save.” It’s worth reading in full, but here’s an excerpt:

Some of it is visual. Yes, it is true that all my posts on Twitter and Facebook look something similar to a personal blog: They are collected in reverse-chronological order, on a specific webpage, with direct web addresses to each post. But I have very little control over how it looks like; I can’t personalize it much. My page must follow a uniform look which the designers of the social network decide for me.

The centralization of information also worries me because it makes it easier for things to disappear. After my arrest, my hosting service closed my account, because I wasn’t able to pay its monthly fee. But at least I had a backup of all my posts in a database on my own web server. (Most blogging platforms used to enable you to transfer your posts and archives to your own web space, whereas now most platforms don’t let you so.) Even if I didn’t, the Internet archive might keep a copy. But what if my account on Facebook or Twitter is shut down for any reason? Those services themselves may not die any time soon, but it would be not too difficult to imagine a day many American services shut down accounts of anyone who is from Iran, as a result of the current regime of sanctions. If that happened, I might be able to download my posts in some of them, and let’s assume the backup can be easily imported into another platform. But what about the unique web address for my social network profile? Would I be able to claim it back later, after somebody else has possessed it? Domain names switch hands, too, but managing the process is easier and more clear— especially since there is a financial relationship between you and the seller which makes it less prone to sudden and untransparent decisions.

But the scariest outcome of the centralization of information in the age of social networks is something else: It is making us all much less powerful in relation to governments and corporations.

Ironically, I tweeted a link, but I think I’m going to try to go back to more blogging, even if the content might fit somewhere else. Hossein’s right. There’s a web here, and we should work to save it.

(Previous mentions of Hossein: Hoder’s Denial“, “Free Hossein Derakhshan.”)

Chaos and Legitimacy

At BruCon 0x06, I was awoken from a nap to the sound of canons, and looked out my window to see soldiers marching through the streets. It turns out they were celebrating the 200th anniversary of the Treaty of Ghent. As I’m sure you’ll recall from history class Wikipedia, the Treaty of Ghent ended the war of 1812, and was the second war between Great Britain and the less Canadian parts of its North American colonies.

Treaty of Ghent Anniversary Celebration

Lately, I’ve been thinking a lot about that and what it tells us about Iraq, ISIS and more recently, Ferguson, and I want to write some of it down to see if it makes sense.

Much of our policy in Iraq and Afghanistan seems to operate on a model of history which goes something like this: after the revolutionary war, town meetings coalesced into the Constitution, and we all lived democratically ever after. It’s an ahistorical view that forgets the Articles of Confederation, the Whiskey Rebellion, Shays Rebellion, and what some in the American south still call “the War of Northern Aggression.” It takes time to develop the institutions of a functioning democratic society.

Is it any surprise that after years of dictatorships, torture of dissidents, children growing up under sanctions (in the case of Iraq), occupation, and civil war, the people of Iraq are not using democracy to solve their problems? That they fight over how to run their country?

While each has a unique history and set of circumstances, it appears to me that there is, across Afghanistan, Iraq, Syria, a crisis of legitimacy. The people who live in those areas have disagreements about not only who should lead them, or what policies should be in place, but about the process for selecting their leaders or governments, and the powers those governments should have.

Their disagreements are strong enough that many people are willing to take up arms rather than acquiesce to other visions. Our understanding of these disagreements is muddied by use of terms like “militia”, “the legitimate security forces” or “the so-called Islamic State.”

The Islamic State, with territory, an army, and a currency, is in many ways, no more or no less legitimate than the army and currency of Prince Assad of Syria. (He is a prince in all but name, having inherited power from his father, that literal inheritance of power being the defining feature of princes.) Assad has taken the step of staging a Potemkin village election, because he understands that legitimacy (rather than power) comes from the consent and agreement of the governed.

This is why Churchill said that democracy is the worst form of government, save all those others that have been tried. No one really thinks that asking a bunch of people who can’t be bothered to vote who should lead them is a great way to get the best people into government. But democracy is a unique way to give people a voice, and in that voice, get their consent. The form democracy, that everyone has a voice, is what gives it its legitimacy. Another way to say that is it’s the ballot or the bullet. (If you haven’t listened to Malcom X give that speech, it’s really an outstanding use of your time. Ballot or Bullet Part I, Ballot or Bullet Part II. In two parts from 100 American Speeches, not sure why it’s two-parted.)

Developing legitimacy requires both institutions and time. The institutions must show that they are reliably better than other choices, or people will pursue those other choices. When Federal grand juries return indictments in 162,000 out of 162,011 cases brought to them, it is reasonable to question if they are a worthwhile or trustworthy institution, or act simply as an instrument of power. From that same 538 Story, grand juries in Dallas reviewed 81 shootings by officers, and returns a single indictment. It is easy to think something is out of whack.

What I think I see in Ferguson is that the institutions of justice have failed, again and again. They didn’t just fail when Darren Wilson shot Michael Brown. Police officers can and will make bad decisions. But afterwards, they continued to fail. The medical examiner didn’t take photos because the battery in his camera died. The prosecutor led Darren Wilson’s testimony.
The institutions didn’t just failed in the moment, they couldn’t be made to work under an intense spotlight. The figures about grand jury indictments indicate that they system is failing victims of police violence. (Although Law Proffesor Paul Cassell makes a case that the grand jury did the right thing, and Wilson had a strong self-defense claim.) However, the institutions didn’t fail completely. A grand jury met, its activity was transcribed and the transcript was released. These elements of transparency allow us to judge the system, and find it wanting. But even while wanting, it’s better than judgement in the ‘court of public opinion,’ and its better than mob justice or lynchings.

These failures may lead reasonable people to ask what alternatives to violence exist? It may lead people to think that violence or destruction is their best option. Perhaps the democratic bargain as a whole is no longer sufficiently legitimate to the people protesting or even rioting in Ferguson. To be clear, I don’t think that the violence or property destruction will improve their lives. In fact I believe that violence and property destruction will make their lives worse. I also think that the people rioting, if they would sit down and talk it through might even agree that burning their own community won’t help. But they’re living in a system where things are more arrest warrants than people.

The chaos in Ferguson, like the chaos in Boston in 1776, like the chaos in Iraq, like the chaos in Syria, may be stopped, for a time, by more violence. But violence will not correct the underlying issues of legitimacy.

(There’s a whole related history of the use of offices to enrich office-holders, including the sale of military commissions, the sale of tax collection jobs, etc. I think that’s too complex for me to work into a single blog post. But briefly, the idea that positions were held as a public trust was an important development. We’ve lost it to the idea that because
officials will sometimes act in their own interest, we should only expect them to act that way. In no longer holding people to an ideal, we’re losing something.)

3D-printed guns and the crypto wars

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?“]

we mutually pledge to each other our Lives, our Fortunes and our sacred Honor


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:

New Hampshire

Josiah Bartlett, William Whipple, Matthew Thornton


John Hancock, Samual Adams, John Adams, Robert Treat Paine, Elbridge Gerry

Rhode Island

Stephen Hopkins, William Ellery


Roger Sherman, Samuel Huntington, William Williams, Oliver Wolcott

New York

William Floyd, Philip Livingston, Francis Lewis, Lewis Morris

New Jersey

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

North Carolina

William Hooper, Joseph Hewes, John Penn

South Carolina

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.

Thoughts on this Independence Day

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.

A few thoughts on chaos in Tunisia

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?

P != NP and Security

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:

  1. P!=NP really isn’t interesting.
  2. 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.
  3. 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.

Nelson Mandela


Twenty years ago today, Nelson Mandela was released from prison on Robben Island, where he was imprisoned for 27 years for considering violence after his rights to free speech and free association were revoked by the government.

I learned a lot about the stories when I visited South Africa, and then more when my mom sent me “The World that was Ours” by Hilda Bernstein. She was an activist and the wife of one of the “Rivonia Trial.” Her book is a highly readable account of what life was like, and how people who started out as reformers were radicalized by increasingly bizarre and ineffectual attempts by the government to exert control.

It also gives a good sense of how absurd the actions of the apartheid system became as time went on. I could make snarky comparisons to the TSA, and believe me, I’m tempted. But the simple truth is that as bad as things have gotten in the US, they generally don’t even approach the dysfunction which existed in South Africa.

Looking at South Africa today, it’s easy to forget that twenty years ago, the country was engaged in an active race war with government forces shooting into funeral crowds every weekend. The work that Mandela, Desmond Tutu, and F.W. De Klerk and others did to stop the violence and build the society which exists in South Africa today is one of the success stories of our time. Yes, it has deep imperfections, but so does the world.

Photo from the Apartheid Museum. On the left is a ballot box.

Today in Tyrranicide History

On January 30th, 1649, Charles I was beheaded for treason. He refused to enter a defense, asserting that as monarch, he was the law, and no court could try him. That same defense is raised today by Milošević, Hussien and other tyrants.

The story of how John Cooke built his arguments against that claim is told in entertaining and accessible depth in “The Tyrannicide Brief” by Geoffrey Robertson.

As his website says, “Geoffrey Robertson QC has been counsel in many landmark cases in constitutional, criminal and media law in the courts of Britain and the commonwealth and he makes frequent appearances in the Privy Council and the European Court of Human Rights.” So he knows what he’s talking about, and he knows how to tell an engaging story.

The principle that no one is above the law is an important one. So today raise a glass and remember John Cooke.

“As far as I know, effective immediately”

Asked about the timing, the unbriefed propaganda minister mumbled: “As far as I know, effective immediately.” When that was reported on television, the Berliners were off. Baffled border guards who would have shot their “comrades” a week earlier let the crowd through—and a barrier that had divided the world was soon being gleefully dismantled. West Germany’s chancellor, Helmut Kohl, was so unready for history that he was out of the country.

The destruction of the Iron Curtain on November 9th 1989 is still the most remarkable political event of most people’s lifetimes: it set free millions of individuals and it brought to an end a global conflict that threatened nuclear annihilation. For liberals in the West, it still stands as a reminder both of what has been won since and what is still worth fighting for.

The Economist has two excellent articles about the wall. “So much gained, so much to lose” and “Walls in the mind.” They do a great job of capturing both the ups and downs of the chaos that has replaced the Politburo and its puppets.

It’s also worth remembering that it’s the 61st 71st anniversary of Kristalnacht.