But what if?
I still owe you Part II of my Darwinism post. But in the meantime, I’d like to pontificate about a fallacy that I’ve seen so often it deserves a name. I’ll call it the But-What-If? Fallacy, after the following joke:
“Let n be an integer…”
“But what if n isn’t an integer?”
The fallacy consists of bringing something up that was specifically defined to be irrelevant. Of course, no one would be silly enough to do that in real life! Except…
- “I would never want to live in a society where people were always happy. Such a society would be a stifling, conformist dystopia, like in Gattaca or Brave New World.”
Well then, people wouldn’t always be happy, would they?
- “If quantum mechanics is nonlinear, then P=NP in the physical world.”
This one makes steam emanate from my ears. Let’s repeat three times: P and NP are purely mathematical concepts. As such, the laws of physics can have no bearing on whether or not they are equal.
(Of course, it could be that PA=NPA where A is a “real world oracle.” But if you understood that point, then you’re already way beyond the “P=NP in the physical world” crowd.)
Continuing:
- “I could never marry a guy I didn’t love, even if he was unfailingly kind, generous, and loyal. I’d never know when he might abandon me.”
- “You shouldn’t take this drug, even if it will help reduce your anxiety. You can reduce your anxiety just as well without it.”
- “Sure, a perfect computer simulation of a human being might hold an intelligent conversation. But could it ever write a poem, or laugh at a joke, or fall in love, or…”
GODDAMMIT! WHAT PART OF “BY ASSUMPTION” DON’T YOU UNDERSTAND?
Sorry, I sometimes get carried away. In the past, my favored solution to the BWI? Fallacy was forcible re-education camps for everyone who commits it. But lately, I’ve come to think that a softer approach might work.
See, the problem is that most people (even theoretical physicists) have very little experience thinking like mathematicians. By nature, people want to keep coming back to the issues they care about, even when you ask them a hypothetical question that defines those issues away. The key is, first, to identify the real question on the other person’s mind:
Are NP-complete problems hard in the physical world?
Is this guy as kind and generous as he seems?
Will this drug really help reduce my anxiety?
Could a computer that writes decent poetry, laughs at jokes, etc. be built?
You can then point out the difference between this question and the one that was asked. Often, the more abstract question won’t even have occurred to the other person. But once the person understands the abstract question — and why it remains, even after the concrete one has been answered — it’s time to extend your hand. “Welcome to the business.”
Follow
Comment #1 January 5th, 2006 at 4:20 am
“You shouldn’t take this drug, even if it will help reduce your anxiety.”
Quite sensible, for taking drugs can cause anxiety…
Seriously, I don’t see how the drug example falls into your category. After all, one may have several reservations about the drug – possible side-effects, the danger of addiction…
Comment #2 January 5th, 2006 at 4:43 am
cheshire cat: Of course. All I meant was that, if you can reduce your anxiety just as well without a drug, then by definition, the drug doesn’t help reduce your anxiety! Here the phrase “just as well” implicitly accounts for side effects, addiction, and anything else in your personal utility function.
Comment #3 January 5th, 2006 at 6:19 am
HI Scott,
Just wanted to point out an issue with this claim:
“P and NP are purely mathematical concepts. As such, the laws of physics can have no bearing on whether or not they are equal.”
While the large majority of folks who have thought hard about the relation between math and physics agree with it, there is a small, but well-respected, minority that argues that this clean distinction between math and physics is not ultimately justfifable.
The most influential argument is due to Quine in “Two Dogmas of Empircism”. A comment is not the place to go into this in detail, but consider what a justification of your claim would have to look like. It would not be a purely mathematical justification, nor would it be purely physical. Instead it would have to depend on a principled distinction between the two things, and Quine claims that you cannot find such a way of distinguishing them that does not just assume that they are distinct.
But of course, making such an assumption would make you guilty of exactly the sort of thing you are complaing about in your post.
By the way, I don’t believe that the people who claim that the nonlinearity of QM would entail that P=NP are sophisticated Quineans. Rather, I just want to suggest that you have made a substantive claim that therefore needs justification, and that this justification is not as easy to provide as it might first appear.
Dave
Comment #4 January 5th, 2006 at 7:25 am
Dave: Thanks for your thoughtful comments, and for the pointer to Quine.
For me, a question is “purely mathematical” if it can be phrased in terms of whether Turing machines halt (in other words, as a Pi_k sentence for some countable ordinal k). By this criterion, the Continuum Hypothesis is not purely mathematical, but P vs. NP, the Riemann hypothesis, and so on certainly are.
In my view, if you don’t accept that a given Turing machine either halts or doesn’t halt on a blank tape, then you might as well question modus ponens, the law of the excluded middle, etc. But in that case, what would it even mean to debate the nature of P vs. NP (or any other question, for that matter)?
Comment #5 January 5th, 2006 at 11:28 am
Scott don’t you know that when most physicists say “in the real world” they are thinking “^(real world oracle)”? 😉
Also while I agree that P versus NP is a “pure mathematical question”, I also hope you’d agree that it is physics that gets to decide whether this question is of any consequence (unless, of course you define consequence by the million dollars you would win for solving the P versus NP problem from the Clay people.) I wouldn’t touch P versus NP with a ten foot pole these days because I believe it is not the relevant real world question. If you showed me PNP tomorrow, I wouldn’t be satisfied until you extended this proof to BQPNP.
Comment #6 January 5th, 2006 at 11:56 am
“Scott don’t you know that when most physicists say ‘in the real world’ they are thinking ‘^(real world oracle)’? ;)”
In that case, even if quantum mechanics is nonlinear, we might still have P!=NP in the real world. Certainly P^PSPACE = NP^PSPACE, but there’s no good evidence that P^#P = NP^#P.
Comment #7 January 5th, 2006 at 12:00 pm
Dave: I have trouble accepting your view of P and BQP. You seem to be saying that you’re bored with P vs NP because it’s too easy, and that you would rather jump straight to the conjecture that BQP does not contain NP.
Maybe my view is unduly timid for modern times. I would be thrilled if someone could show that P does not equal PSPACE.
Comment #8 January 5th, 2006 at 12:13 pm
“I wouldn’t touch P versus NP with a ten foot pole these days because I believe it is not the relevant real world question. If you showed me PNP tomorrow, I wouldn’t be satisfied until you extended this proof to BQPNP.”
I was debating this question with Michael Nielsen in Australia. Two interesting points:
(1) Mike would go even further than you. If you showed him that NP is in BQP, he wouldn’t be satisfied until you extended that to a proof that BQP=QMA. 🙂
(2) Starting from quantum computing, there ought to be many ways to recover the classical computing model without putting it in at the outset. One way would come from my conjecture that every set of quantum gates is universal (under, say, BQL reductions) for one of four complexity classes: BQL, ParityL, P, or BQP. If the conjecture is true, then P pops out, even though the question itself only referred to complexity classes that are kosher for physicists!
Mike told me about an analogous phenomenon, where the notion of a “classical channel capacity” pops out while studying quantum channel capacities. Can you think of other examples? 🙂
Comment #9 January 5th, 2006 at 12:23 pm
The original post touches upon the broader point that there are many forms of broken logic in the big bad world. People ineptly rigorize questions and claims all the time. Typically they aren’t even loyal to the strange suppositions that they invent. In the end, I agree with Scott that mathematical training makes you a better person, not just a better mathematician. It doesn’t by any means supercede underlying illogical, emotional human nature, but it at least helps.
Certainly one common mode of bad logic is the throw-away assumption that Scott mentions. “Even if I knew he was loyal, I still wouldn’t trust him.” But it isn’t by any means the only kind. Another common one is to freely conflate logical truth with truth asserted by a trusted authority. I remember a common mantra after the OJ Simpson trial: “In this country, you are innocent until you are proven guilty.” I.e., they lost the distinction between objective innocence and a legal presumption of innocence.
Another pet peeve: When people do the math completely correctly, yet still refuse to believe the answer. There have been studies about this in introductory physics courses. My wife mentioned the cute example fact that if you saw a baseball bat in half crosswise at its center of mass, the two halves do not have equal weight. According to the studies, it is incredible what it takes to get the average undergraduate to really believe this. If the professor asserts it and they do the calculation themselves, then maybe 15% believe it. If in addition, they see the real demonstration in class, then still only 40% (I think) believe it; the other 60% cling to the idea that it’s a visual deception.
Comment #10 January 5th, 2006 at 12:30 pm
Greg: I didn’t mean to suggest that P versus NP is boring. I only meant to suggest that we have no idea whether proving separations like BQP versus NP (or BQP versus PSPACE) are easier or harder than proving P versus NP (or P versus PSPACE.) Since I’m a physicists, and worship at the alter of quantum theory, I have a hard time dealing with P (channelling Feynman: “the world isn’t classical damnit!”) I’d put my money on the fact that quantum computers should be used to define the fundamental complexity classes. And if this is true, should we be surprised that proofs in quantum complexity are “simpler” or “easier.” (And actually, as Scott says Michael Neilsen suggests, we should really be talking about BQP versus QMA.)
Comment #11 January 5th, 2006 at 12:54 pm
Dave: I can assure you that it is no easier to show that BQP does not contain NP than it is to show that P does not contain NP. Maybe at some intuitive level the switch to BQP is an important hint, but logically speaking it’s a harder question.
I guess I’m not sure what you mean by “I wouldn’t touch P versus NP with a ten foot pole”. I took “boring” as a paraphrase of your figure of speech, but maybe you mean something else.
As I said, my hat will be off to you if you can establish that any two classes between P and PSPACE are not equal. You are free to pick BQP and QMA if you think that that helps your intuition. Logically speaking, it only makes the question harder.
(You are not free to demur that PSPACE is not quantum, because, as everyone knows, PSPACE = BQPSPACE.)
Comment #12 January 5th, 2006 at 2:31 pm
Greg: “I can assure you that it is no easier to show that BQP does not contain NP than it is to show that P does not contain NP. Maybe at some intuitive level the switch to BQP is an important hint, but logically speaking it’s a harder question.”
Um, I’m arguing exactly your last sentence. Certainly since P is in BQP showing BQP!=NP implies that P!=NP. But I’m not talking about hardness here in terms of complexity separations, I’m using hardness here to mean how hard is it for us mere mortals to write down a proof. I believe that since the universe obeys quantum theory, using the universe’s natural language is more likely to lead us to proofs. Of course this is a TOTALLY subjective arguement with little (no?) evidence in its favor. However, when it comes to intuition about how to prove something, using nature as my guide feels a lot better than ignoring nature.
Comment #13 January 5th, 2006 at 2:58 pm
“See, the problem is that most people (even theoretical physicists) have very little experience thinking like mathematicians.”
Really, Scott, you have to get over this bigotry against theoretical physicists you seem to have… 🙂
As for the relative importance of P=NP vs. BQP=QMA, consider the following. Computer science is more than just mathematics in that in that it attempts to describe an actual physical thing, namely computation. The “science” in computer science is the ability to refute theories of computation by experiment. For example, the construction of quantum computers seems to refute the Turing machine model of computation.
Definitively refuting a computational model by experiment is, however, challenging at best and impossible at worst. The problem is that some of these models (including the Turing machine model) only claim to be accurate asymptotically with caveats like “up to a polynomial factor,” whereas experiments can only probe finite-instance computations. Nevertheless, one can amass “evidence” from experiments that the model of computation is wrong, but there is always a danger that true asymptotic behavior only becomes apparent at larger-sized instances. Once in a while, though, clever thinking can lead to experiments that show that entire classes of theories are incapable of accurately modeling experimental results, as in the case of Bell’s Theorem from quantum mechanics.
So what does this have to do with P=NP vs. BQP=QMA? Well if at some point there is definitive experimental evidence that P is not an accurate model of computation (i.e. the Church-Turing thesis is false), which would be an extremely exciting result, then the question of whether P equals NP or not would be akin to the question of whether the angels that push the planets around have two wings or four. As Dave Bacon wrote, “physics gets to decide.” The only caveat I would add is that, due to the asymptotic nature of computational models, it could be the case that sometimes even physics can’t decide!
Just as “physics decides” whether the P=NP question is less relevant than the BQP=QMA question, so too would I say that physics decides whether the P=PSPACE question is less relevant than the question suitably generalized to account for general relativity. The PSPACE model implicitly assumes a Euclidean geometry for the (infinite) tape, but Einstein has taught us that geometry can’t be taken for granted in some Kantian way but instead must be measured. It is quite possible that there are ways to harness spacelike hypersurfaces in interesting GR spacetimes to solve problems outside of PSPACE yet which only utilize a polynomial amount of this hypersurface.
Comment #14 January 5th, 2006 at 3:00 pm
“Even if I knew he was loyal, I still wouldn’t trust him.”
This is not an example of a logical fallacy. When someone says this, it’s an acknowledgement of their “imperfection” as a human: The fact that their emotions will supersede their ability to react rationally to a situation.
You cannot simply interpret spoken English as though it appears in a mathematical proof. The sentence really means “Even if I knew he was loyal, I still couldn’t trust him because trust is not only a function of his loyalty, but also a function of my emotional state.”
Comment #15 January 5th, 2006 at 3:03 pm
Do you think that classical gravity would be easier to describe using “quantum language” since it’s the “natural language of the universe”?
Comment #16 January 5th, 2006 at 4:10 pm
Dave: Your real point is one that I already acknowledged. Sometimes it is easier to prove something stronger or more general, because rephrasing it is a good hint for finding the proof. You expect the concept of BQP to be an important hint for establishing complexity separations. Certainly Scott has already made use of it to reprove a non-separation, namely that PP equals its Boolean closure.
But still, for a question as hard as P vs PSPACE, I have to take your enthusiasm for BQP for this question as sheer speculation. I agree completely that BQP is more fun than a barrel of monkeys. So I don’t disagree with you at all that BQP could be useful for proving these separations. But I am also unqualified to agree more than epsilon.
Comment #17 January 5th, 2006 at 5:56 pm
“using the universe’s natural language is more likely to lead us into proofs”
yeah, right. Quantum mechanics it the “natural language” of the universe, which is why it was discovered 250 years after classical mechanics.
Comment #18 January 5th, 2006 at 6:07 pm
“Quantum mechanics it the “natural language” of the universe, which is why it was discovered 250 years after classical mechanics.”
Thousands of years before classical mechanics there was this idea that objects only moved when they were pushed.
Comment #19 January 5th, 2006 at 7:11 pm
Dave and cheshire cat: Whoa, whoa, break it up. 🙂
I do think QM is in some sense the “natural language of the universe.” But I also think that even in QM, classical information has a distinguished role to play (see my last comment for some results/conjectures making that more precise). On this question, I unexpectedly find myself agreeing with Bohr.
Comment #20 January 5th, 2006 at 7:19 pm
“Do you think that classical gravity would be easier to describe using quantum language since it’s the natural language of the universe?”
Yes! In just the same way that Newtonian gravity is much easier to understand once one sees it as a limit of GR.
anon2
Comment #21 January 5th, 2006 at 7:19 pm
Either you misunderstand me or you’re being disingenuous. Of course quantum mechanics describes the universe accurately at small scales. But the correctness of a physical theory has no significant relation to the value of the mathematical concepts it engenders. Newton and Leibniz gave us calculus, which was far more fundamental to the development of mathematics than anything that arose from quantum mechanics…
What physicists like you fail to understand (or purposely choose to ignore) is that P vs NP is just as important a mathematical question as it is a question about the nature of computation. While the reduction of computation to physics may be satisfying for those with a monological world view, the richness of the question and of the classical theory it is part of remain unaccounted for…
Scott speculates about ways to recover the classical model from the quantum model. But it would be just as interesting, if not more, if quantum complexity classes could be defined without direct reference to the mathematics of quantum mechanics… P and NP have compelling definitions in terms of models of logical theories which make no reference to ambiguous concepts such as “time” and “non-determinism”.
Comment #22 January 5th, 2006 at 7:34 pm
“But it would be just as interesting, if not more, if quantum complexity classes could be defined without direct reference to the mathematics of quantum mechanics…”
Indeed some of them can, like PostBQP and BQPSPACE.
On the other hand, whether there’s a definition of BQP itself that doesn’t “smack of quantum” is a question I still regard as open.
Comment #23 January 5th, 2006 at 7:59 pm
“Yes! In just the same way that Newtonian gravity is much easier to understand once one sees it as a limit of GR.”
This is an idiotic statement.
Comment #24 January 5th, 2006 at 9:10 pm
“This is an idiotic statement.”
This is the sort of blog comment I love: pure vitriol, undiluted by content.
Comment #25 January 5th, 2006 at 9:19 pm
One solution would be to turn off anonymous comments.
Comment #26 January 5th, 2006 at 9:20 pm
“…P and NP have compelling definitions in terms of models of logical theories which make no reference to ambiguous concepts…”
As does the correct description of QM.
idiot
Comment #27 January 5th, 2006 at 9:23 pm
“The problem with the Global Village is the Global Village Idiot.” – Paul Ginsparg
Comment #28 January 6th, 2006 at 1:07 am
An alternative view: Quantum mechanics cannot be the “language of nature”, or at least it cannot be the last word in physical description; and one can say this a priori, on the grounds that phenomenological concepts like “measurement” and “observable” are ontological primitives in the theory. This is why we have “ontological interpretations” of quantum theory (Bohm, Everett, etc.) – because people sense that QM is inherently incapable of being a fundamental theory.
Now where does this leave quantum information theory, and in particular, proposals that the quantum theory of computation – not classical computer science – is the ‘real’ theory of computation? I think about it like this: There is an ensemble of logically possible worlds. To discuss which one we might be living in, two things are required – an ontological ‘meta-theory’, which takes a stand on questions of pure ontology (e.g. what is a ‘state’, what is a ‘property’), and a ‘physical’ theory which unambiguously picks out a particular class of the worlds from the meta-theory. (The various ontological interpretations of QM combine these two requirements, advancing both ontological and physical propositions.)
Any fundamental theory of computation – along with mathematics in general – resides at the ontological level. As such, the classical theory of computation is better suited to such a role. Quantum information theory is more akin to Bayesian probability theory – it’s an “agent’s-eye” view, grounded in phenomenological rather than ontological concepts.
Comment #29 January 6th, 2006 at 1:38 am
Incidentally, this approach suggests a way to make “NP-complete problems are physically hard to solve” into a physical principle, i.e. into a postulate that guides theory formation. As Scott points out, whether P=NP is a question about the capabilities of Turing machines (and their Turing-equivalent peers). One could define an oracle which by construction solves problems in P, in NP, and in any other class you like, in O(1) time – but this would have no bearing on whether P=NP; to think that it did would be to fall victim to the But-What-If? fallacy.
Now think ontologically for a moment. Suppose our ontological meta-theory stipulates that a possible world must consist of entities that have states, that undergo changes of state, and whose changes of state result from interaction with other entities. A Turing machine in the classic mold – a read-write head moving back and forth on an infinite tape – is therefore a possible “world”. So is our O(1) oracle.
Now define physical time to be measured by the number of discrete changes of state in an entity. Assuming P!=NP, we can then say: in a “Turing world”, NP-complete problems cannot be solved in polynomial physical time, but in an “oracle world”, they can. “NP-complete is hard”, as a physical principle, means that we should only consider Turing-world physical theories.
Comment #30 January 6th, 2006 at 2:08 am
Mitchell: Thanks for the comments! You might want to check out this survey paper — especially the last section, which is all about whether we should adopt the hardness of NP-complete problems as a principle of physics.
Comment #31 January 6th, 2006 at 5:08 pm
For a perspective from a mathematician:
Freedman
has a nice short article on topological perspectives.
idiot
Comment #32 January 7th, 2006 at 12:09 pm
Another good one is when someone asks you what you would do if your company went bankrupt, then takes answering that question as evidence of indifference as to whether the company goes bankrupt.
With regards to studying quantum computation, anyone who does so should do it with full realization that there’s a good chance, if not a likelihood, that there life’s work will be rendered completely uninteresting by new understandings of physics. Quantum mechanics contradicts relativity, computation, and common sense. While we have evidence that common sense loses, the other two are causes for concern.
Scott, given a question of whether a machine which has a special black box command which it can ask whether a turing machine halts will ever itself halt when given a specific program, do you consider that to be ‘purely mathematical’ as well?
Comment #33 January 7th, 2006 at 5:25 pm
“Scott, given a question of whether a machine which has a special black box command which it can ask whether a turing machine halts will ever itself halt when given a specific program, do you consider that to be ‘purely mathematical’ as well?”
Yes. I explicitly allowed for such questions in my previous comment, when I referred to Pi_k sentences for any countable ordinal k. (Sorry if that term is unfamiliar. Basically, it means that you get a Turing machine with an oracle for the halting problem with an oracle for the halting problem with an oracle for the … as many times as you like.)
Comment #34 January 8th, 2006 at 5:15 pm
Scott, do you accept machines which have access to an oracle corresponding to an uncountable oracle?
Comment #35 January 8th, 2006 at 7:29 pm
Bram, what do you mean by “uncountable oracle”?
Comment #36 January 8th, 2006 at 11:16 pm
Sorry, I meant ‘uncountable ordinal’. That was a typo.
Comment #37 January 9th, 2006 at 12:03 am
Bram, it’s not clear what it would mean to have a Pi_k sentence where k is an uncountable ordinal. With Pi_omega, you get the halting problem, halting problem to the halting problem, etc., any finite number of times. With Pi_{omega+1}, you get the halting problem for Pi_omega machines, and so on for any countable ordinal. If a were an uncountable ordinal, then I don’t know how you would define Pi_a sentences in terms of Pi_b sentences for b<a.
Comment #38 January 9th, 2006 at 12:19 am
I don’t know either 🙂 But it seems reasonable to state ‘see this infinite serious of countable ordinals? Generalize that and be able to query about any of them’. Which (and I’m basing this much more on intuition than actual knowledge) would seem to put you in the unpleasant position of having to guess whether statements of the existence of particular large ordinals are consistent in order to accept or not the meaningfulness of whether a particular machine with a corresponding oracle ever halts.
Comment #39 January 9th, 2006 at 12:54 am
The whole point of my criterion was that, no matter how abstract a sentence looks, it should always boil down to whether ordinary Turing machines halt.
Once you throw that away (say, by going to uncountable ordinals), the sentences you construct might still have definite truth-values, but I’ll no longer bet my life on it. 🙂
Comment #40 January 9th, 2006 at 1:01 am
Bram: Rereading your last post, you might be hung up on a simpler definitional issue. An ordinal is countable if it has a countable number of predecessors. In particular, the following two operations always keep us inside the countable ordinals:
(1) “And so on, creating an infinite hierarchy.”
(2) “See that infinite hierarchy? Define a new machine that can query it anywhere.”
To get to uncountable ordinals, we’d have to stipulate a new operation that went beyond (1) and (2).
Comment #41 January 9th, 2006 at 1:02 am
Note: Here “countable” means finite or countably infinite.
Comment #42 January 9th, 2006 at 1:07 pm
So you aren’t willing to accept Mahlo then?
I suspect it’s possible to come up with a definition of an oracle which corresponds to Mahlo. Of course, to actually work out the details I’d have to understand Mahlo itself, which I suspect is a ‘super-generalization’ of ‘you see that sequence? generalize it’.
If I ever find myself with nothing to do for a few months I’d really like to become well versed in this stuff, unfortunately the chances of that happening are pretty slim. Until then, I’m just a dilettante.
Come to think of it, any oracle corresponding to mahlo would have to have a way of describing the machines it’s plugging into the oracle, so if mahlo is inconsistent it would just result in a potential circularity in the repeated subtraction, so the question is still mathematically well-defined, it just might not halt because of infinite recursion.
Comment #43 December 21st, 2006 at 7:59 pm
[…] With this post, I begin an occasional series called Mistake of the Week — in which I’ll explore “obvious” howlers that nevertheless show up in many different contexts, are made by people who should know better, and do real damage in the world. If you like, you can retroactively consider my post But What If? to be part of this series. […]