Possibly the best thing ever to happen to my inbox
Just a quick (but important) announcement: theorist-extraordinaire and friend-since-back-in-undergrad Ryan Williams reports that the Theoretical Computer Science Stack Exchange website is now up in beta! What is this TCS Stack Exchange? It’s a place where you can post your questions about theoretical computer science and get informed answers to them—intended as the homegrown CS theory analogue of the wildly-successful Math Overflow site. From an initial perusal, the TCSSE looks awesome. Indeed, the only small suggestion I can make is to propose a motto:
The TCS Stack Exchange. Exponentially better than emailing Scott Aaronson.
Update (Sep. 10): While I’m on the topic of announcements, the early registration deadline for FOCS’2010 in Las Vegas is September 30. Hope to see many of you there!
Another Update (Sep. 14): There’s now a beautiful talk by Ken Clarkson, Ron Fagin, and Ryan Williams looking back on the Deolalikar affair and explaining the problems with the proof, which I recommend in the strongest terms to anyone who followed this story. (And yes, I think “looking back” is the right term here.)
Follow
Comment #1 September 4th, 2010 at 8:46 pm
Great news, indeed!
Thanks for informing the community.
Comment #2 September 4th, 2010 at 9:03 pm
Great…I’ve queued up my standard answer for TCS stack exchange: “Why don’t you email Scott Aaronson, I’m sure he’ll know the answer to your question.” 🙂
Comment #3 September 4th, 2010 at 9:09 pm
@Scott: LOL!
@Dave Bacon: RFLOL!
Comment #4 September 4th, 2010 at 9:37 pm
Cool, checking it out now, and if I have any questions, I’ll shoot you an email 😉
Comment #5 September 4th, 2010 at 10:47 pm
That’s great news.. thanks a lot for sharing mr. Scott Aaronson, I hope they don’t think I am a spammer because I have a lot to ask 🙂
But rest of readers don’t be misled! Scott Aaronsons is exploiting the Pagerank algorithm to relief its inbox. Knowing he is an authority, he refers to another entry in order to raise its authority ! Too bad Dave Bacon saw through this clever plan and devised an exploit of his own 😛
Comment #6 September 5th, 2010 at 2:15 am
I prefer blogging with my email.
Comment #7 September 5th, 2010 at 8:59 am
Exponential as a function of what?
Comment #8 September 5th, 2010 at 9:47 am
The length of the question.
Comment #9 September 5th, 2010 at 7:10 pm
I have used MO before, but I am afraid I did not have a good experience. I think the “standards of discourse” policy is taken far too seriously there. Even legit questions that perhaps are not to the taste of the moderators or say the majority are whipped (with down votes) and closed. I found it odd to say the least, and quite shocking. I had a different view of mathematicians (as open to new ways of thinking, new ideas, new definitions etc.) but MO provides overwhelming evidence to the contrary in the form I outlined above.
So my question is this: will TCSSE follow suit, or is it going to be a less authoritarian community? By authoritarian, I mean along the following lines: we only think as research oriented, that which fits with our current definitions of concepts, our current tastes, and by “our” we mean those in power. We shall not think as research oriented things that we are not working on, things we don’t like, or things we don’t find interesting.
Note that I am not saying that we allow homework questions, ill-posed questions, or plain meth-headed garbage.
My concern is that if TCSSE says it is for research oriented discussion, then it must stick to an open and broad definition of what it means by research-level. It can’t mean pet topics of a few researchers.
I have seen this happen far too often on MO, and I am afraid that since there will be overlap in the moderators between MO and TCSSE, it will happen at TCSSE too.
And if that happens, then I am afraid I will have to withdraw from using TCSSE as well, as I have from MO. 🙁
Comment #10 September 5th, 2010 at 7:19 pm
I have also been told in the past that MO is privately funded, so it can do whatever it wants. (Is this true?) Is TCSSE privately funded too?
IMHO, there are many activities involved in doing math, including coming up with new definitions, discussing notions, toying with ideas etc. All of this can be done at a serious research level or at the garbage/crank/ill-posed level. MO is hard-headed and excludes all but a very few activities: for example, the “textbook question” style for MO is to ask a question about something that is well-defined and well-known to the majority of the community, and to ask whether something about it is true or not. As I say above, this is only but a part of what goes into doing mathematics. But MO of course, is not interested in anything but questions of this type, and this, it labels as what it means by “research level discourse.”
It would be unfortunate if TCSSE goes the same way. It would hurt participation.
Comment #11 September 5th, 2010 at 8:23 pm
@Quantum: There have been quite a few discussions on meta.MO about the merits of the somewhat stringent closing policy, but many of us longtime readers (such as myself) have come to agree with it. Note that questions of all fields (provided they are research-level) are accepted; the preponderance of algebraic geometry is, nonetheless, intriguing.
Besides, there is a new general math Q/A site which appears to be going well; it includes many respected mathematicians as contributors. (I feel kind of guilty for having asked a bunch of n00b alg. geo. questions on MO but now ask them on math.SE and still usually get good answers.)
If anything, I’d say that MO has been a fantastic success in attracting top-notch mathematicians *because* of its tight quality control. I fear that math.SE might tend to drift away from that, but so far that does not seem to have happened.
Comment #12 September 5th, 2010 at 9:13 pm
Scott, people don’t want answers from experts, they want answers from Scott Aaronson! You can make your announcement about TCSSE more effective by answering a few questions on TCSSE (let’s say once a week). I can assure you that it will make your inbox way happier. 🙂
Comment #13 September 6th, 2010 at 4:23 pm
As brilliant as you maybe Dr.Aaronson, you are a little self-obsessed. Actually a lot.
But thanks for the link.
Comment #14 September 8th, 2010 at 1:45 pm
Great link, Scott, I’m hooked! I don’t even need to ask questions, all the good newbie ones have been asked and answered with plenty of references.
Comment #15 September 13th, 2010 at 12:25 pm
Golly … only one post on Shtetl Optimized in the past week … and similarly unprecedented lassitude on The Quantum Pontiff.
Folks, it was inanition that killed-off Kurt Gödel; let’s not let anything similar happen to QIS!
Sooner-or-later, Scott will be blogging/publishing the wonderfully interesting research he’s been doing with Alex Arkhipov, and I’m expecting there will be a torrent of (deservedly) favorable commentary upon it … this will be good for QIS.
To help keep folks’ QIS passions warm in the interim, I posted an (intentionally provocatively optimistic) QIS vision over on Quantum Pontiff.
The common-sense point being, that to keep our passions warm, we can either embrace provocatively optimistic research visions, or we can court and marry passionate nightclub dancers … both of which Kurt Gödel very wisely did. 🙂
Comment #16 September 14th, 2010 at 11:54 am
Ok, I have one question though which is not appropriate for Stack Exchange: how do computer scientists read each other’s papers? I’m talking about: how do you actually find and download a copy of a paper you want? 90% of the time that I look for a TCS paper, I find that it requires payment to view, even if I am using the library of a major university. This doesn’t happen in physics except on very, very rare occasions, since almost all libraries have subscriptions to the major journals, such as Phy Rev, and even if you aren’t at a university almost all physics content since roughly the mid-’90s (exact time depending on subfield) is available on the arxiv. But in TCS the supposedly most important results (those in FOCS/STOC) are unavailable online, unless I’m missing some easy trick, and even lots of journals require payment.
So, am I just missing something? Sometimes I can find a paper on a personal webpage, but in general, no. What do you, Scott, do if you want to read a paper from STOC ’98, for example without going to get a physical copy?
Comment #17 September 15th, 2010 at 9:37 am
I like the car analogy by Terence Tao in the powerpoint slides.
I think D. seriously lacks the ability to solve the P vs NP problem. He doesn’t understand the problem and the tools he was using well enough. HP should find another principal research scientist to replace him!
Comment #18 September 15th, 2010 at 12:05 pm
Just to point out the obvious, if researchers are judged by their worst ideas and articles, then few scientific or mathematical reputations survive intact (hmmm … maybe none at all?).
A classic example is Nature editor’s John Maddox’s famously wrong solution of the 3D Ising model … which mistake did little harm to Maddox’ subsequent career. Needless to say, numerous further examples of grossly wrong articles by famous scientists and mathematicians could be cited.
This is the point of Wolfgang Pauli’s famously acerbic dismissal of a colleague’s work: “It is not even wrong.” So far, no-one has said that of Deolalikar’s work! 🙂
Thus, there is no need to rush to judgment regarding Deolalikar’s work; in the long run, the article that emerges from peer review is what matters. And this is why peer review—far more than “weblog review”—serves the STEM community well.
Comment #19 September 15th, 2010 at 4:07 pm
Continuing John’s point;
Isaac Newton, generally regarded as the greatest scientist, wrote a huge amount. There was a note in Scientific American in the 1960’s about the final volume of his complete works being finally published. As I recall, it was the fourth and biggest, the theological writings, some of which were about being a son of God, or something like that. That made me sit up and say WTF? (Darn! I should have copyrighted that expression!) Has anyone out there read that volume? If so, kindly provide a summary.
Comment #20 September 15th, 2010 at 10:50 pm
I’m actually curious about what matt said. If anyone would care to reply on how they get they’re articles, whether it’s by paying, through inter-library loan or online, please share!
My current school only has ACM journals for free but SIAM and some of the others are actually the only ones available that have certain articles of interest. I would hate to pay $25 per article and find out there’s a better approach to acquiring them.
Thanks!
Comment #21 September 17th, 2010 at 3:18 am
You can find most TCS articles by typing the title into google with filetype:pdf.
Comment #22 September 17th, 2010 at 4:40 am
Hmmm, I’ll give that a go, thanks!
Comment #23 September 17th, 2010 at 12:20 pm
Sometimes that works, sometimes not, especially not for older papers. But seriously: that’s the model for how to find papers in TCS? Hope that someone has a copy you can locate by searching? Perhaps (apologies in advance…) this is what comes of people saying things like “TCS is no more about computers than astronomy is about telescopes”….one forgets that computers do actually exist, and are capable of all kinds of amazing things, from designing planes to picking your driving route to solving surprisingly large instances of NP-hard optimization problems to (drum roll….) helping exchange scientific information.
Comment #24 September 17th, 2010 at 4:16 pm
A terrific quote from a terrific book is Avi Wigderson’s aphorism “We are successful because we use the right level of abstraction”, which introduces “Section 1.1.2 Characteristics of Complexity Theory” in Oded Goldreich’s Computational Complexity: a Conceptual Perspective.
In this regard, an aspect of the Deolalikar episode that has pretty severely rattled my faith in the naturality of TCS is the recognition that membership in P is formally undecidable.
In engineering, we are often concerned to validate and verify our algorithms, and thus any class for which membership is undecidable seems terribly unnatural. After all, in the real world we almost never have access to an oracle that promises “This algorithm is in P” … instead we are required to figure it out for ourselves.
Taking Avi’s advice, I’ve been looking around for a subclass of P for which, on the one hand, membership *is* (at least formally) decidable, and yet on the other hand, is powerful enough to capture our intuitions of what (in practice) “proper” algorithms are capable of computing.
This proves to be a frustrating exercise … in the sense that neither Oded’s book nor the Complexity Zoo are much help (to me, anyway). Does such a class exist, even in principle? If it does exist, can it be concretely separated from P? Might this question (if suitably formalized), be suited to the TCS Stack Exchange?
Wikipedia has a page on the Curry-Howard correspondences which seems to point in the desired direction (and I would like to thank Greg Crosswhite, who directed me to this correspondence):
————
Because of the possibility of writing non-terminating programs, Turing-complete models of computation (such as languages with arbitrary recursive functions) must be interpreted with care, as naive application of the ( Curry–Howard correspondence ) leads to an inconsistent logic. The best way of dealing with arbitrary computation from a logical point of view is still an actively-debated research question, but one popular approach is based on using monads to segregate provably terminating from potentially non-terminating code (an approach which also generalizes to much richer models of computation, and is itself related to modal logic by a natural extension of the Curry–Howard isomorphism.
——-
Any QIS expert who cared to deconstruct the above (to me wholly opaque) passage, or more broadly, was willing to comment upon any aspect of TCS relating to the restriction of P to algorithms that certifiably are in P, would help to relieve at least one engineer of confusion regarding the naturality (or lack thereof) of P≠NP … and also help provide intellectual sustainment to this fine TCS blog! 🙂
Comment #25 September 18th, 2010 at 4:12 am
James, if your school subscribes to JSTOR, you can find some older papers that way.
John Sidles, membership in P of the language recognized by some Turing machine being undecidable shouldn’t be surprising if you know about Rice’s theorem. In logic, you hit undecidability as soon as you try to do almost anything interesting. That doesn’t make TCS unnatural any more than it makes Peano arithmetic unnatural. It’s more surprising when something (like real closed fields) turns out to be decidable than when it’s undecidable. The reason lower bounds proofs are so hard is that we usually only deal with the familiar, decidable and understood fragments of P and it’s very hard to quantify over whatever else might be “out there”.
The Curry-Howard (CH) correspondence is from constructive logic and has nothing to do with QIS. The point of that paragraph you quoted is that for any effective theory T no matter how powerful, there will be Turing machines that halt on every input, but that T can’t prove halt on every input. So again, it’s hard to use CH to prove anything about the farther-out Turing machines.
You might look for the paper “Total Functional Programming” if you want to see a proposal for programming only with certifiably computable functions (not necessarily polynomial-time).
Comment #26 September 18th, 2010 at 7:13 am
asdf Says: “The reason lower bounds proofs are so hard is that we usually only deal with the familiar, decidable and understood fragments of P and it’s very hard to quantify over whatever else might be ‘out there.’ “
————-
Asdf, that well-written sentence very aptly summarizes an aspect of P≠NP that has been slow to dawn up me … for which thank you very much! 🙂
And can’t you make the same point even more strongly? By replacing “very hard to quantify” with “impossible even in principle to quantify”?
Here’s a proposition, in the form of an Alice-and-Bob story, to make this point clearer. Suppose Alice’s job is to write obfuscated code in P, while Bob’s job is to separate P from NP. Thus an essential part of Bob’s job is to separate Alice’s obfuscated code from NP.
Now we relativize Alice’s capabilities, by providing her with an oracle that decides membership in P. How much harder does Bob have to work, when challenged by obfuscated code from P-relativized Alice … a person we will call “Alice^P”?
Well, it’s pretty clear Alice^P can play tricks that are utterly beyond mortal Alice. For example, she can interleave any algorithm with a (formally undecidable) mortal matrix computation. By this means, Alice^P can “spoof” Bob with a code that claims to be in P, but (unprovably by Bob) is not.
What seems unnatural to engineers is that the standard definition of P≠NP matches Bob not against Alice, but against Alice^P … a person who has relativized capabilities that don’t exist in the real world.
Thus, a more natural definition of P—from a practical engineering point of view—would be restricted to exclude algorithms that can be crafted only by (relativized) P Alice^P. Let us call this restricted class P’.
Now, while proving P’≠NP might be easier than proving P≠NP, working with the non-relativizing class P’ presents us with new hard problems (as usual). For example, can we exhibit concrete algorithms that are in P but not P’ ? Or is such an exhibition impossible, even in principle?
To conclude … it might be a fun TCS challenge, relating both to abstract notions of relativization and to concrete notions of code obfuscation, first to construct and then to contemplate, a concrete algorithm in P but not P’ … so bring on the mortal matrices! 🙂
Now, is *this* the kind of problem that is suitable for TCS Stack Exchange? Here comments are welcome.
Comment #27 September 18th, 2010 at 3:17 pm
John, it would help if you spelled out more formally what you mean about obfuscating code, deciding membership in P, etc. What do you even mean by an algorithm being in P? P is a class of languages, not algorithms. An algorithm can be polynomial time or not. A language is in P if there is a polynomial-time algorithm that recognizes it, not necessarily a -known- P-time algorithm. So we don’t know if 3SAT is in P, for example, even though we know non-P-time algorithms to recognize it.
An example of a possibly P-time algorithm whose complexity might be undecidable: for input x (a binary number of length n bits), check all even numbers 2
Comment #28 September 18th, 2010 at 3:18 pm
My previous reply got cut off somehow.
An example of a possibly P-time algorithm whose complexity might be undecidable: for input x (a binary number of length n bits), check all even numbers 2
Comment #29 September 18th, 2010 at 3:19 pm
John, it would help if you spelled out more formally what you mean about obfuscating code, deciding membership in P, etc. What do you even mean by an algorithm being in P? P is a class of languages, not algorithms. An algorithm can be polynomial time or not. A language is in P if there is a polynomial-time algorithm that recognizes it, not necessarily a -known- P-time algorithm. So we don’t know if 3SAT is in P, for example, even though we know non-P-time algorithms to recognize it.
Oh I see, WordPress saw a less-than sign and thought it was an HTML tag. I’ll try again:
An example of a possibly P-time algorithm whose complexity might be undecidable: for input x (a binary number of length n bits), check all even numbers 2<a<x in increasing order. If any of these a’s is not the sum of two primes, return 1, otherwise return 0. This algorithm is exponential-time if Goldbach’s conjecture (GC) is true, and (asymptotically) constant-time if GC is false. Note that undecidability is relative to the theory you’re working in, too. GC might be independent of Peano arithmetic but provable with calculus (“second-order arithmetic” in logic terminology). Or it might be independent of second-order arithmetic but provable with large cardinals, or whatever.
Comment #30 September 18th, 2010 at 3:27 pm
Oh yes, just because there’s lots of undecidable questions about a complexity class doesn’t mean you can’t prove anything about the class. For example, that the halting problem is undecidable by a Turing machine is easy to prove by diagonalization. For a while people hoped that P!=NP could be proved the same way, but it didn’t work out.
There are many problems that are provably not in P, like the truth of sentences in Euclidean geometry. Those are decidable by a theorem of Tarski about real closed fields, but the decision procedure has complexity O(2**2**n) or something like that. Definitely outside P, but also definitely outside NP and even outside PSPACE. An arbitrary language L (even if known to be decidable) is not necessarily in P. The P vs NP problem asks if a certain additional piece of information about L is enough to tell you that L is in P. The additional information is of course that L is in NP. So really, the problem asks whether NP has a special, special property, and it’s very hard because right now we know so little about what NP really is.
Comment #31 September 18th, 2010 at 7:21 pm
asdf asks: John, it would help if you spelled out more formally what you mean about obfuscating code, deciding membership in P, etc.
Asdf, formalizing these ideas is exactly what I’ve been thinking about (for fun). Because as Han Solo memorably said (and effectively Avi Wigderson’s aphorism says too), “Well, that’s the trick, isn’t it?”
All that I have in mind at present more closely resembles a (half-finished) Borges story than a starting set of mathematical definitions and propositions.
Without going into details—which requires several paragraphs—the narrative centers upon Alice’s mind-numbing clerical job of validating algorithms with the help of a pair of magic eight-balls (which are oracles for membership in P and NP ).
One day, Alice comes to work … and those oracular eight-balls are gone … her job is no longer purely clerical … she is thrown upon her own computational resources.
A key question is, what computational resources are most natural to postulate for Alice? And here the meaning of natural is easy … natural resources are those that lead to strong TCS theorems and compelling narratives.
It is far from clear (to me) that the common practice of providing Alice with oracular eight-balls is the sole path to a compelling TCS narrative … if only because Alice deserves a stronger motive for character development than that! 🙂
Comment #32 September 18th, 2010 at 7:38 pm
John, what do you mean by an oracle that recognizes membership in P? What is the input to the oracle supposed to be?
Comment #33 September 18th, 2010 at 9:52 pm
Asdf, by definition a “P-validating oracle” accepts as input a Turing machine, and the oracle answers “accepted in P ” if and only if the Turing machine always terminates in a state that is either “accepting” or “rejecting” after a time that is polynomial in the length of an (arbitrary) input supplied to that Turing machine; otherwise the oracle answers “rejected from P “.
The above is (to my understanding) the sole definition of the complexity class P , in the sense that no other (known) definition of P is non-trivially equivalent to it.
The P-validating oracle is so incredibly powerful—it solves even undecidable problems with ease—that perhaps it is unsurprising that P is hard to separate from NP … it’s because the awesome power of P’s oracle shields us from learning anything concretely useful about P … heck, we can’t even decide what algorithms are members of P.
From an engineering point-of-view, the awesome relativizing power of the P-validating oracle; seems unnatural … and yet (obviously) it’s not so easy to specify a concrete decision procedure, associated to a restricted class P’, that would reasonably encompass our notions of what “real” computers can do.
Because no matter what concrete validation for the class P’ we propose as being “good enough” … it seems that the oracle could (in principle) show us how to extend P’ concretely … if necessary, by adding new axioms to our mathematics.
Hopefully the above isn’t *entirely* misguided … or if it is, some kind person will set the record straight regarding P-validation.
Comment #34 September 19th, 2010 at 4:21 am
John, that doesn’t recognize P at all. P is a set of languages, not a set of Turing machines. Let’s say you write a program to solve 3SAT with the obvious exponential time algorithm. Your oracle says that algorithm is not polynomial-time. But that doesn’t mean 3SAT is not in P. What you really want the oracle to say is whether there is a P-time machine that recognizes the same language as the TM you have given to the oracle.
To say that a machine M halts on every input, and does so in polynomial time, says “there exists c such that for every input x, the computation M(x) halts in less than (|x|**c + c) steps.” If I have it right, this is what’s called a Sigma-0-2 proposition, which is “beyond undecidable”, i.e. even a machine with an oracle for the halting problem can’t decide it.
You actually want “M halts on every input and there is a P-time machine M’ that recognizes the same language as M”. “M halts on every input” is “for all x, there exists c such that the computation x halts within c steps”, a Pi-0-2 proposition, again if I have it right. It’s interesting that this has a different quantifier shape than that M halts in P-time. Maybe I got it wrong and someone can tell me.
To combine these, I think you’d say “for all x, there exists (c,d,M’) such that M halts within d steps, M’ halts within (|x|**c+c) steps, and M(x)==M'(x)”. So this again is Pi-0-2, again harder than the halting problem.
What is kind of interesting is that you can view a decidable language L as an equivalence class of machines MM(L) that recognize L. Then L is in P if some member of MM(L) is a polynomial-time machine. And it turns out (I think) that there is an effective procedure for generating (codes of) machines M1,M2,M3… such that they all run in P-time and halt on all inputs, and for every language L in P, a machine recognizing L appears somewhere in that sequence. Where there is (I think) not such a procedure to generate codes of machines M1,M2,… such that there’s a recognizer in the sequence for every language in R (the class of recursive languages). So in this sense, P is recursively enumerable but R is not. That would seem to suggest some hope of proving P!=NP by induction over some carefully concocted well-ordering of the sequence generating the machines that recognize all the languages in P. This is the “pseudoproof” I mentioned a while back, and seems like an obvious enough idea that I wonder if there is a known barrier against it. Of course the barrier might be that “obvious” actually means “obviously wrong” ;-).
Comment #35 September 19th, 2010 at 6:20 am
A little bit late, but thanks asdf for the heads up!
Comment #36 September 19th, 2010 at 9:08 am
Asdf, I don’t think we’re differing fundamentally … but rather, we’re discussing issues that are very tough to describe in a few blog paragraphs … unless we embrace Aaronson-style pedagogic prestidigitation to finesse some tricky issues … and even then it is very tough to be rigorous.
One sleight-of-hand that my narrative employed came right at the beginning, in the phrase “Alice’s mind-numbing clerical job of validating algorithms”.
Implicit here is that Alice’s job is restricted to some uniform model of computation, in the sense that what Alice receives each morning is a finite, concrete description of a class of Turing machines that is claimed to accept-or-reject (in P ) a language that is implicitly defined solely by that finite, concrete Turing machine description … and Alice’s sole job is to evaluate the claim of membership in P.
The preceding uniformity-centric narrative is motivated partly by the discussions in Oded Goldreich’s short essay On Promise Problems: in Memory of Shimon Even (1935–2004) and also by Oded’s wonderful new book P, NP, and NP-Completeness, and partly by the concrete task of verifying and validating (V&V) that systems engineers face every day.
In particular, the story of “Alice’s Job” is very strongly influenced by Oded’s view—expressed in the Shimon Even memorial essay—that “P is the class of promise problems that are solvable in (deterministic) polynomial time” for which “the promise need not be an easily recognizable set.”
It was then only necessary to ask the Ferengi question: “Hmmm … so membership in the class P is not easily recognizable? How does that work, exactly?”, upon which the narrative of “Alice’s Job” begins to construct itself (with plenty of help from Oded Goldreich’s writings, to be sure).
But please don’t imagine that anyone (especially me) knows how Alice’s story ends. 🙂
Comment #37 September 19th, 2010 at 7:01 pm
John, one issue is you’re using terminology in what I think is a nonstandard way. A language L is set of strings, not a Turing machine. P is a set of languages, i.e. a set of sets of strings, not a set of Turing machines. Some languages can be identified with sets of Turing machines, but only nonconstructively. What do you mean by “a finite, concrete description of a class of Turing machines at is claimed to accept-or-reject (in P )…”? What would such a description look like? What does it mean to accept-or-reject something in a set of sets of strings? I ask this because I’m not sure we’re going from the same basic definitions. This situation is like in calculus, where you can use derivatives in engineering by knowing some intuition and some differentiation formulas, but proving theorems about them requires precise definitions of things like limits (“for all epsilon>0 there is a delta>0 etc. etc.”) Any discussion of high-level philosophical stuff is going to be vague and fuzzy unless it is grounded in solid understanding of the basic definitions.
At an even further-out level, it’s just not that useful to look at P vs NP in engineering terms. It’s a problem in mathematical logic and (like the graph minor theorem) its resolution may be completely outside of the realm of the practical, even if it turns out that P=NP.
I like Knuth’s answer to W. Gasarch’s poll (http://www.cs.umd.edu/~gasarch/papers/poll.pdf):
Donald Knuth: (Retired from Stanford) It will be solved by either 2048 or 4096. I am currently somewhat pessimistic. The outcome will be the truly worst case scenario: namely that someone will prove “P=NP because there are only finitely many obstructions to the opposite hypothesis”; hence there will exists a polynomial time solution to SAT but we will never know its complexity!
Comment #38 September 19th, 2010 at 9:58 pm
ASDF says: “one issue is you’re using terminology in what I think is a nonstandard way”
LOL … asdf, we have Oded Goldreich to thank for pointing out—in his essay On Promise Problems—that there *is* no uniquely natural “standard” for talking about P≠NP. Here I have in mind this passage from the essay (both the words and the emphases are Oded’s):
———–
“The common perception by which promise problems are useful for treatment of some abnormal situations is in my opinion wrong. On the contrary, in my opinion promise problems are the norm: indeed the standard and natural presentation of natural decision problems is actually in terms of promise problems, although the presentation rarely refers explicitly to the terminology of promise problems.”
———–
My little narrative Alice’s Job was an attempt to distill an Oded-ary perspective on the P≠NP problem into a short Borgesian story involving characters having natural human motivations. In particular, Alice’s Magic Eight Ball is—or at least, is intended to be—a concrete physical manifestation of the real-world promissary aspects of P≠NP.
Oded’s a great mathematician and an outstanding writer … but even he needed 32 pages to cover these issues in his essay!
If anyone else cares to attempt a translation of Oded’s essay into an ultra-short Alice-and-Bob narrative … please be my guest … the attempt is bound to be interesting for both authors and readers. 🙂
Comment #39 September 19th, 2010 at 10:52 pm
asdf,
Great stuff, and thanks for the tips on
(1) googling .pdf (duh, why didn’t I think of that) and
(2) checking out Gasarch’s poll.
(2.1) I think Andy Klapper has a good point that the problem should be called the “P and NP” problem.
(2.2) Check out Sariel Har-Peled’s example of why P and NP is “completely useless”. I disagree, I think it is 99% useless (for practical application), perhaps as useful as Fermat’s last theorem. But I think P and NP is a great theoretical problem, just like FLT.
Comment #40 September 20th, 2010 at 2:50 pm
Gosha, whether one views the P≠NP problem a “99% useless (for application)” is largely contingent on whether it is conceived as a deep problem or a wide problem. There are plenty of textbooks and weblogs that espouse the “deep” point-of-view, but the “wide” point-of-view is finding increasingly many adherents … Oded Goldreich’s text belongs to this vanguard.
Characteristic of the “deep” point-of-view is a desire to stick strictly to the formal definition of the problem … characteristic of the “wide” point-of-view is a willingness to flex the starting assumptions.
From the “wide” point-of-view, the crux of the P≠NP problem is associated to validation: if we are given a Turing machine that claims to accept a language in P, by what (non-oracular) means can we validate that claim? And if there is no (non-oracular) means that is wholly reliable—and thus no concrete means of instantiating some of the languages in P—then is the definition of P really natural? Perhaps it would be more natural to exclude from P those languages that we cannot instantiate?
These are the kind of “wide” questions that modern TCS textbooks like Oded’s encourage us to ask. For which we can all be grateful—especially young people!
That’s my 2¢. 🙂
Comment #41 September 21st, 2010 at 8:40 am
Over on Dick Lipton’s blog Gödel’s Lost Letter and P=NP, Gil Kalai has been asking similar questions about uniformity. And if Gil is confused, imagine how confused I must be!
Gil’s questions amount to asking whether a polynomial-depth hierarchy of circuits, circuits that design circuits, etc. (in effect, FPGAs) could instantiate Alice’s Magic Eight Ball oracle, or a reasonable approximation to it. This further illustrates that P≠NP isn’t just a deep problem, it also is a wide problem.
Comment #42 September 21st, 2010 at 2:12 pm
I’ll admit I’m taking a somewhat narrow view, that the P vs NP problem is that thing that you have to solve to win the Millenium Prize for solving it, and that problem has a narrow definition.
It is logically possible that P!=NP uniformly but P=NP non-uniformly. IIRC, uniform simply means that given n, there is an efficient way to generate the circuit C(n). So “P=NP nonuniformly” would be true if there is some fixed constant d, such that for every n, there is a circuit C(n) with n**d+d gates that solves SAT on n variables; but actually constructing C(n) might take O(2**n) Turing machine steps. So if you had an arbitrary problem instance of size (say) 623, to solve it with that poly-size circuit C(623), you’d first have to do a 2**623-sized computation to figure out the circuit.
Comment #43 September 21st, 2010 at 3:05 pm
asdf says: “It is logically possible that P!=NP uniformly but P=NP non-uniformly.”
That is a very nice way of putting it, asdf. And there are many further variations on the same theme, e.g.: “P!=NP uniformly is provably true, but P=NP non-uniformly is undecidable.”
That is why (IMHO) the narrowly-based criticism of Deolalikar’s proof technology—although that criticism is formally correct—has missed the main broad point; that point being, if Deolalikar’s proof technology can be adapted to prove (for example) a restricted theorem along the lines of “P!=NP uniformly”, then Deolalikar will lose-out on a Millenium Prize, yet still have proved an immortal result in TCS … with the latter aspect being (by far) the more important consideration.
For this reason, it might have been better had the Clay Institute split the P vs NP prize in two: one for P vs NP uniformly, the other for P vs NP non-uniformly, with the solution to each problem being worth one million dollars (since they are comparably valuable IMHO).
In working out the details of splitting the P vs NP problem along these lines, some risable technical possibilities suggest themselves … which this weblog column is too narrow to contain … until such time as Alice and Bob find themselves embodying these TCS realities at Alice’s Job ! 🙂
Comment #44 September 21st, 2010 at 3:40 pm
A non-uniform P=NP result would be very interesting from a theoretical point of view and sounds likely to have powerful consequences for average-case complexity. It would mean approx. “if you can break one 256-bit AES key by brute force, you can break as many additional ones as you want with very little extra effort each”. But I don’t think the non-uniform version of the problem holds the same sort of fascination as the uniform one, which says there’s a way to break a single key in the first place.
Re the Millenium prize, sure, I’m all in favor of more of them. I could use a million bucks, and if they get indiscriminate enough about giving them out, I’d have more of a chance 😉
Comment #45 September 21st, 2010 at 6:13 pm
Thanks for your comments asdf … it’s taken awhile for me to grasp that the Turing machines of the strict Millenium Prize P vs NP problem definition are restricted to have a finite number of states, and in this sense are uniformly describable … but this description is not accompanied by any documentation or validation requirement whatsoever … meaning that membership in P is in effect promised by a powerful (but how powerful?) oracle.
In the memorable words of Gen. Buck Turgidson of the film Dr. Strangelove: “Gee, I wish we had one of them oracles!” … because it is clear that such an oracle in itself has the capacity to solve broad classes (but how broad?) of hard problems (but how hard?).
I mention this solely in the hope of assisting that small set of Shtetl Optimized readers who have been even more confused than me regarding issues relating to verification and validation in TCS/QIS … accepting that very plausibly this set is the empty set. 🙂
Comment #46 September 21st, 2010 at 8:56 pm
I don’t think there’s any promise or oracle involved. The idea is that you can have a pure, nonconstructive existence proof that P=NP.
It doesn’t even seem so terribly troubling. For decades, people used the simplex method to quickly solve every linear programming problem they cared about in practice, even though nobody really knew the complexity of linear programming or the simplex method. It turns out that LP is in P, and the simplex method is P-time for all but certain pathological cases in which it’s exponential. So imagine a simplex-like algorithm for SAT, which empirically is polytime for all instances anyone tries it on, and in fact is -always- polytime, but not provably so. One depressing (or exciting, depending on your viewpoint) thing about logic is quickly learning that decidable problems are the exception rather than the rule. The only thing to do is stop being bothered by it.
Did you read Scott’s paper about possible formal undecidability of P vs NP?
You might also like some of Chaitin’s books about undecidability, though his writing style can be annoying.
Comment #47 September 21st, 2010 at 9:34 pm
One more thing: AFAIK, uniformity means the run time of the TM that generates C(n) is polynomial, not just that the number of states in the TM is finite (that number is always finite).
If P=NP then there is a d such that the max circuit size for n-input SAT is O(n**d) and there is a trivial approx. O(2**n**d)-time algorithm for generating the circuit C(n) for any n. Just enumerate all circuits with n inputs in order of increasing size, and test each circuit on all 2**n inputs until you find the smallest one that solves SAT for every input. That TM doesn’t need very many states and it even runs in polynomial space. It just needs a heck of a lot of runtime.
Comment #48 September 22nd, 2010 at 5:28 am
asdf: … Decidable problems are the exception rather than the rule. The only thing to do is stop being bothered by it.
Hmmm … and yet, asdf, maybe there are further alternatives? To inspire us, we have Gödel’s construction of concrete undecidable problems … which by meta-mathematical reasoning are true. And this leads us to the following sequence of questions.
—————————–
Q1 Do Turing Machines (TMs) exist that accept a language in P, but do not provably do so?
Q2 If so, can we exhibit such a machine? That is, can we exhibit its explicit finite tuple ⟨ Σ, Γ, Q, δ ⟩, in the notation of Stephen Cook’s Millennium Prize definition?
Q3 If we cannot exhibit these TMs—and in particular, cannot verify them if an oracle presents them to us—what is the obstruction to exhibiting/verifying/constructing them?
Q4 If such TMs exist, and yet we can neither exhibit nor verify nor construct them, then how does this restrict viable proof strategies for separating P from NP (the point being that these are among the TMs that we must separate)?
—————————–
One funny property that this particular class of TM’s has is that its members can easily win any obfuscated code (OC) contest, on the grounds that we can supply them with any finite input, and watch their finite workings halt in finite (polynomial) time … and yet we can never (even in principle) prove that these TM/OC devices will always halt.
That is why a concrete instance of a TM in this “ultimately obfuscated” would be an algorithm to contemplate with awe. Moreover, if such a TM cannot be verifiably instantiated, that obstruction too could be contemplated with awe, as yet another barrier to settling P vs NP .
So the answers to these questions are interesting, no matter what the answers turn out to be.
Comment #49 September 22nd, 2010 at 2:52 pm
Your comments, if you please:
http://www.bris.ac.uk/news/2010/7216.html
Comment #50 September 22nd, 2010 at 4:13 pm
John, “provability” is relative to a given set of axioms (like PA, ZFC, or whatever), so you have to keep that in mind. With more powerful axioms you can prove more stuff. That said, your questions are fairly easy exercises and it might be more beneficial to try to figure them out yourself. Here is a hint for Q1/Q2: imagine that the Twin Primes Conjecture is undecidable in ZFC and go from there.
Comment #51 September 22nd, 2010 at 4:16 pm
Dave asks: You comments, if you please.
Without presuming to dictate topics for Shtetl Optimized, it certainly is true comments on the above (linear optics) experiment would indeed be *very* welcome.
Leaving aside the (difficult) task of doing calculations having practical utility, the reported linear optics experiment is a substantial step toward achieving a broader two-part challenge: (1) acquire an experimental data-set that provably cannot be simulated by a Turing Machine in P , and then (2) verify that the data-set has the promised property.
Both of these challenges are mighty tricky—tricky in terms of math, science, *and* engineering—and (AFAICT) both Scott and Alex Arkhipov have been thinking about these challenges long-and-hard. The various discussions relating to oracle devices and verification protocols earlier in this weblog had their origin largely in Scott and Alex’s recent lectures on the TCS/QIS of linear optics experiments, specifically with regard to the oracular aspect of the experimental data-sets, and the verification aspect of the subsequent analysis.
Comment #52 September 22nd, 2010 at 4:52 pm
asdf Says: imagine that the Twin Primes Conjecture is undecidable in ZFC and go from there …
… to construct a Turing Machine that runs in PTIME , for arbitrary input, if and only if the (nominally undecidable) Twin Prime conjecture is true.
Hmmm … is that *really* an “easy exercise”? Not to me! So if you were to post a description of such a machine, one (or even both) of us would be enlightened! 🙂
Comment #53 September 22nd, 2010 at 7:53 pm
Assume TPC (twin prime conjecture) is unprovable. There is an obvious Turing machine that on input x, finds the first prime pair (p,p+2) with p>x, then halts answering “yes” regardless of what x was. If TPC is true, this machine accepts all inputs, a language definitely in P. If TPC is false, then for sufficiently large x, it never halts. You can substitute other expressions for TPC in obvious ways.
Note I did not say this machine runs in ptime, but only that (per your original question) the language that it recognizes is in P (assuming TPC is true). Obviously in this case there is another machine that runs in ptime trivially and recognizes the same language.
I think it is the case (but I’d have to do some reading to be sure) that if algorithm A recognizes a language L in P, then there is another algorithm B that recognizes the same language L and provably runs in p-time. I’m not sure if it’s necessarily provable (even though it’s true) that A and B accept the same language, however. I don’t really get the impression that this type of question is of much interest to mainstream CS theorists, but I don’t really have much clue what they are thinking.
Comment #54 September 22nd, 2010 at 8:41 pm
asdf says: : I think it is the case (but I’d have to do some reading to be sure) that if algorithm A recognizes a language L in P, then there is another algorithm B that recognizes the same language L and provably runs in p-time. I’m not sure if it’s necessarily provable (even though it’s true) that A and B accept the same language, however.
Thanks, asdf … any references you might provide would be very welcome. If true, that would be a very powerful theorem … although my own feeling is that it plausibly is not true, which makes me even more eager to learn of it. Other TCS experts definitely are welcome to chime in.
Obviously this class of questions is of immense interest to engineers, because the questions reflect practical problems of code verification and validation … not to mention code obfuscation.
As for these questions being “of interest to mainstream CS theorists” … well … that partly reflects the available theorem-proving technology … which perhaps (at present) is not up to the challenges that this class of verification question poses?
Comment #55 September 22nd, 2010 at 8:55 pm
I should have been a bit more specific, this type of question probably isn’t so interesting to abstract complexity theorists (the types of folks who work on P vs NP) as opposed to theorists in general. Provability issues are probably more interesting to programming language theorists since one of the more active approaches to software verification is to embed formal constructive logic directly into programming languages. P vs NP is not a verification problem; it’s a question about the existence or nonexistence of an abstract machine with a certain property.
The thing about algorithms provably in P is from my quick skim of Robert Bellantoni’s PhD thesis a while back, which gives a syntactic characterization of P (see also http://www.cs.toronto.edu/~sacook/homepage/ptime.pdf ).
Formal decidability isn’t that helpful anyway, because of the intractability of proof search. The notorious Japanese “fifth generation computer project” of the 1990’s was going to use Prolog to find all proofs and algorithms automatically, and got nowhere.
Comment #56 September 22nd, 2010 at 10:19 pm
Oops, sorry, I meant Stephen Bellantoni, not Robert. I think I’ve mentioned that result a couple of other times and may have made the same mistake then too :(.
Comment #57 September 23rd, 2010 at 8:36 am
Asdf, I want to thank you very much for your excellent comments. What I have in mind eventually is (perhaps) to post Q1-Q4 (above) on the TCS Stack Exchange.
A truly good TCS Stack Exchange problem is well-posed, novel, solvable, yet not trivially solvable, and broadly interesting. Your comments have greatly helped with the first four (although there is still considerable work to do).
With regard the the fifth criterion of “broad interest”, here are three sentences (which I composed mainly to clarify my own thinking).
—————
(1) Broadly across the global STEM enterprise, there is burgeoning interest in issues associated to formal TCS concepts like “oracle”, “promise problems”, “simulation”, “naturality”, “instantiation”, and “verification and validation.”
(2) This interest arises because modern simulation codes, when suitably verified and validated, serve as oracles that promise success to enterprises, whether the products of these enterprises are instantiated algorithmically as computations, informatically as databases, physically as devices, or all three (as is often natural).
(3) The scale of the enterprises that humanity ventures upon in the 21st century will be largely conditioned by the quality of the oracles that advise us; thus we have powerful motivations to extend the capabilities of our oracles as deeply and as widely as feasible.
—————
Our QSE Group’s experience has been that the challenge of verification and validation—which at first sight seems either easy, or else (and paradoxically) intractable—is the single toughest aspect of building real-world oracle devices, databases, and simulation codes.
Hence our interest in crafting TCS Stack Exchange questions that capture some of the mathematical essence of this challenge.
Comment #58 September 23rd, 2010 at 12:31 pm
asdf, I responded to your (helpful-as-usual) post … but it disappeared into filter-land. As Dick Lipton says, “oh well”.
In any case, perhaps further discussion can fruitfully await such a time as Shtetl Optimized—or any of the CS/QIS/QIT blogs—hosts linear quantum optics as a topic … which is a major practical focus of these verification questions (per Dave’s post #49 above).
Dick Lipton’s current topic Are Quantum Impossibility Proofs Possible?—together with the attendant comments—is helping to set the stage for appreciating and discussing some terrifically interesting aspects of this exciting new class of quantum experiments.
Comment #59 September 25th, 2010 at 7:40 am
This comment is in no way related to the post above, but you’ve closed comments on https://scottaaronson-production.mystagingwebsite.com/?p=188 .
If it’s the case that the Greeks could have invented QM simply by considering a vector with L2 length 1 … shouldn’t we be doing the future a service and develop a probability theory about vectors with L3 length = 1?