Last week I attended the Army Research Office sponsored Workshop on Reasoning in Adversarial and Noncooperative Environments related to Topic #22 of the 2011 MURI. Most of the attendees were AI types many of whom look at games with incomplete information against opponents you can't trust. A group at USC talked about their work using game theory to deploy federal air marshals on planes and road-side checking at LAX. Game theory that might save lives.
I talked in a panel on the complexity of computing equilibrium on why we should turn the question around and use computational complexity to redefine equilibrium. Bart Selman, also on the panel, talked about his limited success in using SAT solving heuristics for QBF. During the Q&A we got into an interesting debate on the importance of computational complexity in real-world scenarios. The word "irrelevant" came up to note that NP-completeness is too blunt a tool to capture hardness in practice. Bart didn't think average-case was quite the right approach either, some other structural property of problems was needed.
Though we both care deeply about satisfiability, Bart and I don't hang out much in the same circles and this workshop was the first time we really had to a chance to chat. Despite the panel, Bart later showed quite an interest in computational complexity. I found myself explaining Ryan's new result to him, which get complexity results from betters circuit SAT algorithms.
The PCP theorem says it is as hard to approximate max-SAT as it is to solve it exactly. In practice, according to Bart, this separation makes SAT easier to solve heuristically. So Bart suggested one might use the PCP theorem as a method to preprocess a formula to improve current heuristics. The PCP theorem still has large constants in the size of the reduction making a direct application impractical. But perhaps parts of the theorem, for example using good error-correcting codes, can help. That would take the PCP theorem, normally used for showing problems hard, to help make SAT easier. Cool if it could be made to work.
Our son has served five combat tours in Iraq and Afghanistan as a US Marine.
ReplyDeleteA notably large proportion of his in-theater activities have resembled an unending sequence of school board and/or a faculty steering committee meetings ...
... interminable, turbulent meetings at which faculty, students, and the local citizenry alike are highly intelligent, heavily armed, justifiably mistrustful, in some cases homicidally angry, and motivated by an ever-evolving admixture of economic desperation, uncompromising religious and political ideologies, and millennia-old ethnic loyalties.
Game theory—aka "common sense"—is of course very useful in these complex, difficult, ever-evolving circumstances. Here we are using von Neumann's pragmatic definition of game theory: "day-to-day—or perhaps year-to-year—opportunistic measures, a long sequence of small, correct decisions."
The nearest thing to a "magic bullet" turns out to be, not the theorems of game theory, but the capability to reliably create dignified, secure, family-supporting jobs. And here the notion of "security" includes, most crucially, a functioning justice system.
Upon this job-associated foundation, all other desired objectives are achievable. Conversely, without this foundation, no other meaningful objectives are feasible.
The seminal document in this regard is FM 3-24 Counterinsurgency, which is available on-line. Our son's in-theater experiences are reasonably in accord with the principles set forth in this document. It is significant, for example, that in FM 3-24 the word "justice" appears more often than the word "victory", and the word "narrative" more often than the word "strategy."
FM 3-24 is a document that well-repays close study. In particular, this morning I posted an essay this morning on Scott Aaronson's blog, upon the relative roles of theorems, postulates, and enterprise in CT/QIT.
That essay claimed to draw upon lessons in Huckleberry Finn ... which is a true claim ... but it is also true that the main ideas of that essay largely originated in a systematic transposition of the key elements of FM 3-24 doctrine to CT/QIT.
The essay was written with a conscious long-term view toward helping this planet's coming generation of young people—young Marines in particular—to find the best possible uses for their youth, their creativity, and their heroism.
And this objective I take to be central not only to complexity theory, but to the entire 21st century STEM enterprise.
Out of subject: I find your blog very interesting and wished you have RSS, for that I could subscribe :)
ReplyDeleteAnon: http://blog.computationalcomplexity.org/rss.xml
ReplyDeletelance, why twitter about wolfram alpha so much ... what is ur obsession with it ?
ReplyDeleteDear Prof. Lance,
ReplyDeleteShould a "but" or an "and" be inserted between (1) The PCP theorem says it is as hard to approximate max-SAT as it is to solve it exactly. (2) In practice, according to Bart, this separation makes SAT easier to solve heuristically.
In particular, what separation is "this" separation? Just want to capture your exact idea here, thanks!!
seems like lance it advertising for the black sheep company. Come on, Lance, if you go like this than Maple should be the one.
ReplyDeleteIn post #10, Anonymous presents an utopian vision:
ReplyDelete-------------------------------
"Governments ... are going to be forced [by transparency] to do less evil and kill less people, topple less democratically elected governments, support less brutal authoritarian dictatorships."
-------------------------------
In post #8, Tinkerpop presents a similar utopian vision (from arXiv:0904.0027):
-------------------------------
"The goal of a eudaemonic system is ... a life that is devoid of pretense, doubt, and ultimately, fear. ... The individual would take on faith that the eudaemonic algorithm knows what is best for them in a resource complex world. Thus, the perfect life is not an aspiration, but a well-computed path."
-------------------------------
I have to say, that IMHO both of these utopian visions might have been issued as press releases straight from the desk of Harry Potter's second-most-evil villain, Dolores Umbridge, in her capacity as an agent of a Voldemort-dominated Ministry of Magic.
At our son's suggestion, I have reviewed a pretty fair selection of the Wikipedia war logs from Iraq and Afghanistan. The non-utopian world they depict—it seems to me—is better described by Hippocrates' aphorism:
-------------------------------
"Life is short, [the] art long, opportunity fleeting, experiment treacherous, judgment difficult."
-------------------------------
It is clear, too, that although Google's motto is "Don't be evil", if it ever should happen that Google *did* become evil, their informatic resources would enable them to be mighty effective at it. And it is far from clear that larger databases, cleverer algorithms, and deeper theorems can provide much protection against this.
This comment has been removed by the author.
ReplyDelete