P ≠ NP ?

Daniel Martin Katz at the Computational Legal Studies Blog just posted this:

P ≠ NP ? [ Vinay Deolalikar from HP Labs Publishes His Proof to the Web, $1 Million Clay Institute Prize May Very Well Await ]

After sending his paper to several leading researchers in the field and acquiring support, Vinay Deolalikar from HP Labs has recently published P ≠ NP to the web. While it has yet to be externally verified by folks such as the Clay Mathematics Institute, it looks very promising. Indeed, this very well represent a Millennium Prize for Mr. Deolalikar. For those interested in additional information, check out Greg Baker’s blog (which broke the story). Very exciting!

This has come up once before on this blog. I’ll paste the previous entry below:

Does P=NP?

If P=NP, then the world would be a profoundly different place than we usually assume it to be. There would be no special value in “creative leaps,” no fundamental gap between solving a problem and recognizing the solution once it’s found. Everyone who could appreciate a symphony would be Mozart; everyone who could follow a step-by-step argument would be Gauss; everyone who could recognize a good investment strategy would be Warren Buffett. It’s possible to put the point in Darwinian terms: if this is the sort of universe we inhabited, why wouldn’t we already have evolved to take advantage of it? – Scott Aaronson (reason #9)

When you have some free time, watch this amazing lecture by Avi Wigderson about one of the great open problems in all of mathematics.

Update, 7/10 1pm: Scott Aaronson thinks there are probably good ideas in the paper, but ultimately he remains highly skeptical this is THE proof.

Advertisement

Quantum Psychology?

Let me be frank; I think “The conjunction fallacy and interference effects” (ungated version) is a horrible misuse of math and indicates an embarrassing failure of peer review.

The author, Riccardo Franco, introduces a parameter that does doesn’t have any foundation in the phenomena it is trying to explain, nor is it shown to aid in modeling.

Please tell me I’m missing something.

What?  You’ve never heard of the conjunction fallacy? It is yet another cognitive bias studied by Amos Tversky and Daniel Kahneman.  They gave people the following problem (quoting from Wikipedia):

Linda is 31 years old, single, outspoken, and very bright. She majored in philosophy. As a student, she was deeply concerned with issues of discrimination and social justice, and also participated in anti-nuclear demonstrations.

Which is more probable?

1. Linda is a bank teller.
2. Linda is a bank teller and is active in the feminist movement.

Does P=NP?

If P=NP, then the world would be a profoundly different place than we usually assume it to be. There would be no special value in “creative leaps,” no fundamental gap between solving a problem and recognizing the solution once it’s found. Everyone who could appreciate a symphony would be Mozart; everyone who could follow a step-by-step argument would be Gauss; everyone who could recognize a good investment strategy would be Warren Buffett. It’s possible to put the point in Darwinian terms: if this is the sort of universe we inhabited, why wouldn’t we already have evolved to take advantage of it?  – Scott Aaronson (reason #9)

When you have some free time, watch this amazing lecture by Avi Wigderson about one of the great open problems in all of mathematics.

Preparing the next generation.

If you’re a regular reader or contributor to this blog, you probably agree that mathematics have an indispensable role in the social sciences. Lately, however, I’ve been thinking a lot about something: what kind of mathematical tools do sociologists of the future require?

The reason I’ve been thinking about this is a talented undergraduate who is strongly considering going to grad school in sociology. Interestingly, part of what has moved him in that direction seems to have been two classes he’s taken with me. The first was the required undergraduate statistics class and the second a substantive class that includes a lot of network analysis, structural theory, and associated material. As it turns out, it’s entirely possible to teach Mayhew & Levinger to undergraduates. Who knew? In any case, in this second class he’s gotten a strong sense that sociology involves a lot of math and this excites him. I’m all for it, since this student is very smart and we need more mathematically-gifted grad students. Yesterday during a conversation, though, he asked me what sorts of math he should be thinking about taking as he prepares for graduate school. I gave him my answers- and an regression analysis textbook to work through during winter break- but I wonder what others think.

If you could somehow start over again in the field, what areas of mathematics would you make sure you learned right from the start?

Which Mathematics to Teach?

In 2002, Paul Lockhart wrote an article about the state of mathematics education called A Mathematician’s Lament.  Lockhart argues passionately that what children are typically taught is neither useful nor interesting.  He believes children would get far more from emulating what mathematicians actually do, unstructured mathematical exploration and proofs.  One of the problems, Lockhart acknowledges, is that many math teachers don’t understand or appreciate what he calls “real math,” leaving them unable to teach it.  While I agree we need to improve our math teaching, and I agree that exposing many more children to “real math” is a good idea, I think Lockhart is at once too optimistic and too pessimistic.

Paul Krugman on Metaphors and Models

Paul Krugman has spent a lot of time recently criticizing economists associated with the Chicago School because he believes they are making horrible public policy recommendations and, importantly, misusing mathematical models, e.g. the oft criticized, dynamic stochastic general equilibrium models. But Krugman has written a lot that is equally interesting, and less political.

Today I’d like to draw your attention to an article he wrote in 1994 entitled, The Fall and Rise of Development Economics.  Its absolutely worth reading the whole thing, but I’ll summarize and excerpt a huge chunk from the middle of it for those of you who are really pressed for time.  Krugman tells us that rigorous modeling is very important for economics, but he also argues that the new (1950s and 1960s) emphasis on modeling led people to forget or ignore things people knew about development economics for years, until people figured out how to model them.

After the break I’m pasting the middle section of the essay, essential reading on metaphors and models:

Mathematical models: why and what for?

An anthropologist friend of mine, Eli Thorkelson, recently asked for my comments on an article by feminist economist Julie Nelson. The article is a critique of rational choice theory (RCT) and I think it has some glaring omissions and misleading claims, but before I get to them I want to briefly offer the positive case for mathematical models, of which rational choice models are a subset.*

Markets and other social phenomena are complex.  We’re never going to have a theory that perfectly describes everything we might want to know about them.  Modeling is one way we can get some insight.  In a model we make some simplifying assumptions and then work out their implications.  Then, and this is key, we do empirical work; we analyze data to see how well our model captures various aspects of the phenomena we are interested in.  Ideally a  model will make predictions that are novel, in the sense that the researcher would not have made them before studying the model, and in the sense that they distinguish one model from another in a way that can be tested rigorously.

What about those simplifying assumptions?  If they turn out to be false, doesn’t that mean the model is junk?