… I know a lot of philosophers who can do math and physics (and some have PhDs in both physics and philosophy).

See more comics from Calamities of Nature

Evolving Thoughts

In the head of John S. Wilkins

… I know a lot of philosophers who can do math and physics (and some have PhDs in both physics and philosophy).

See more comics from Calamities of Nature

Chocosophy
#### The Endarkenment

Read More

Philosophy has always used metaphors of light and vision for wisdom and knowledge. A famous book, Rorty’s Philosophy and the Mirror of Nature (1979), discussed these visual metaphors in detail. We speak, rather too casually, of the Enlightenment, which in German is the Aufklärung, and in French the Lumières, both visual…

Epistemology
#### I’m about to give a keynote… in Poland

Read More

This is a brave new world. I’m about to give a keynote address to the Naturalizing Religion conference in Kazimierz Dolny in Poland. Or I would be if their internet hadn’t just died completely. Stay tuned for further news of the way things go wrong at the very last moment…

Epistemology
#### You and me, baby, ain’t nothing but mammals

Read More

The song of the title of this post is a catchy and highly amusing piece that suggests that if we’re just mammals we should have sex. It’s sort of a low brow version of Andrew Marvell’s To his coy mistress. Instead of Time’s wingéd chariot, we should do what mammals…

Comments are closed.

Manage Cookie Consent

To provide the best experiences, we use technologies like cookies to store and/or access device information. Consenting to these technologies will allow us to process data such as browsing behavior or unique IDs on this site. Not consenting or withdrawing consent, may adversely affect certain features and functions.

No information is sold or given to third parties. See our T&Cs.

No information is sold or given to third parties. See our T&Cs.

The technical storage or access is strictly necessary for the legitimate purpose of enabling the use of a specific service explicitly requested by the subscriber or user, or for the sole purpose of carrying out the transmission of a communication over an electronic communications network.

The technical storage or access is necessary for the legitimate purpose of storing preferences that are not requested by the subscriber or user.

The technical storage or access that is used exclusively for statistical purposes.
The technical storage or access that is used exclusively for anonymous statistical purposes. Without a subpoena, voluntary compliance on the part of your Internet Service Provider, or additional records from a third party, information stored or retrieved for this purpose alone cannot usually be used to identify you.

The technical storage or access is required to create user profiles to send advertising, or to track the user on a website or across several websites for similar marketing purposes.

I’m still waiting for someone to come up with bad philosophy based on the problem of P=?NP. It may just be that they are waiting for that to be solved before they do anything. However, the problem by nature has so many easy soundbite explanations that I’m quite confident it will be heavily abused once it is resolved. Soundbitedness seems to be the main criterion for attracting such abuse.

Philosophers couldn’t do that: it’s just too hard.

Now, where did I put that Löwenheim/Skolem paradox?

I’m here all week. Try the veal.

Yeah, but are they

postmodernphilosophers?As for P vs. NP, some might say that tying NP to human creativity (as some have done) is overreaching, philosophically speaking. I personally don’t think it’s overreaching, so it’s not bad philosophy to me. Misunderstanding NP has certainly led to bad physics, e.g. “nature can solve NP-complete problems in polynomial time”; “quantum computers can test an exponential number of possibilities simultaneously, thereby solving NP-complete problems in polynomial time”.

Lyle? Has anyone actually claimed that quantum computers can have solve NP complete problems in polynomial time? A quantum computer can solve factoring in polynomial time using Shore’s algorithm but that’s a much weaker claim.

I would incidentally argue that tying NP to human creativity is massive overeach since the problem type being discussed are all very rote, not the sort of thing that creativity often comes into play.

Yes, people have made that claim. Do you read Scott Aaronson’s blog? Check out the saga of Geordie Rose and D-Wave.

NP-hard problems are not rote by nature. The ones studied in CS theory courses tend to be rote, yes, but NP as a class includes many interesting natural problems. Take the problem of natural language processing: if we define it as finding a model of language that explains all existing human utterances, we can easily argue that it is NP-hard. The space of possible models is exponential in size, but any given model can be verified in polynomial time (in the size of the number of natural language sentences). The whole field, then, is about coming up with creative heuristics that do a good enough job of solving problems most of the time. Furthermore, every single human child (apart from some that are developmentally disabled) is able to learn some heuristic for this problem. Proving theorems is another (more classic) example of an NP-hard problem that we are able to apply creative heuristics to and solve some instances some of the time. If NP=P, there would certainly be no need for human mathematicians any more; mathematical creativity could be fully and efficiently automated.

Lyle,

As I understand it Georgie Rose claimed merely that he could use D-Wave to get better approximate results for NP-complete problems. See for example: http://www.technologyreview.com/computing/18495/page3/

I disagree with your assesment of NP-hard problems. There are of course a number of different issues here. There are many problems which are NP-hard that are not NP-complete. For example, it isn’t hard to show that if one has a halting oracle then one can use it to solve NP problems in polynomial time. Thus, in one sense HALT is NP-hard even though it obviously is not in NP.

If P=NP, human mathematicians would still be needed. Mathematical creativity is not limited to such problems but also to much more difficult problems that cannot be easily modeled as a single NP complete problem. Given a reasonably complicated axiomatic system “Is there a proof of Y of length l or less?” is in NP. “Is there a proof of Y?” is not in NP. Human ingenuity will thus still be helpful.