Proof vs. Truth in Computational Complexity

Oded's comments

I think Boaz's preface/introduction of his own article is worthy of reproducing, although I don't agree with a few side points he makes (probably semi-jokingly and/or while being carried away).

Most importantly, I do not think we should accept the norms of other sciences that encourage blurring the difference between highly likely conjectures and facts. However, I indeed welcome any attempt to develop notions and measures of the plausibility of conjectures.

In general, I have mixed feelings regarding this paper. On the one hand, I appreciate very much Boaz's advocation of providing more arguments towards various beliefs. Indeed, stating and using beliefs (or assumptions) is far from new to TOC, and ditto w.r.t articulating them, but Boaz's text makes all of this more explicit and justifiable (i.e., he does argue for the benefit of beliefs over sheer skepticism, sometimes too far to my taste...). Furthermore, I like the idea of people expressing views that go beyond the solid facts. On the other hand, I disagree with some of Boaz's specific assertions and/or choices. For details, see the last section of this web-page. (Clearly, the ``mix'' strongly leans to the positive side...)

The original introduction

Theoretical Computer Science is blessed (or cursed?) with many open problems. For some of these questions, such as the P vs NP problem, it seems like it could be decades or more before they reach resolution. So, if we have no proof either way, what do we assume about the answer? We could remain agnostic, saying that we simply don't know, but there can be such a thing as too much skepticism in science. For example, Scott Aaronson once claimed that in other sciences "P neq NP" would by now have been declared a law of nature. I tend to agree. After all, we are trying to uncover the truth about the nature of computation and this quest won't go any faster if we insist on discarding all evidence that is not in the form of mathematical proofs from first principles.

But what other methods can we use to get evidence for questions in computational complexity? After all, it seems completely hopeless to experimentally verify even a non-asymptotic statement such as "There is no circuit of size $2^100$ that can solve 3SAT on 10000 variables". There is in some sense only one tool us scientists can use to predict the answer to open questions, and this is Occam's Razor. That is, if we want to decide whether an answer to a certain question is Yes or No, we try to think of the simplest/nicest possible world consistent with our knowledge in which the answer is Yes, and the simplest such world in which the answer is No. If one of these worlds is much nicer than the other, that would suggest that it is probably the true one. For example, if assuming the answer to the question is "Yes" yields several implications that have been independently verified, while we must significantly contort the "No" world in order to make it consistent with current observations, then it is reasonable to predict that the answer is "Yes".

In this essay, I attempt to do this exercise for two fascinating conjectures for which, unlike the P vs NP problem, there is no consensus on their veracity: Khot's Unique Games Conjecture and Feige's Random 3SAT Hypothesis. This is both to illuminate the state of the art on these particular conjectures, and to discuss the general issue of what can be considered as valid evidence for open questions in computational complexity.

See ECCC TR12-120

Digest and Critique

I wish to start by commending Boaz for writing an essay of the current nature, which is not only of a great value as an overview of important developments but also has the added value of offering well-articulated views regarding them.

I think that Boaz's suggestion for an Occum Razor consideration (regarding how assumptions fit with known facts) makes much sense, but I would not present it as the only possibility. Also, in using this criterion, I'd focus on simplicity not nicety (which is far a less sound notion, let alone that its relevance here is unclear).

In my analysis, Boaz offers four examples of ``supportive evidence'' (where none of these are logically sound, but are rather supported by the Occum's principle):

1. If the known (hardness and algorithmic) results regarding two problem are similar, then this is evidence for their having similar complexity. [E.g., a few lines above Sec 1.1]
2. If there exist tight lower and upper bounds for a wide range of natural problems and one of these bounds depends on an assumption, then this is evidence of the validity of the assumption. [E.g., first paragraph of Sec 1.1]
   In general, if an assumption yields consequences that are believable but not proved otherwise, then this is evidence for the assumption. This holds especially if the assumption was suggested prior to deriving the conclusion and more so without intending it. [E.g., second paragraph of Sec 2.1]
3. The current state of the ongoing ``battle'' between algorithms that work on ``natural'' instances and instances that are hard for ``natural'' algorithms is evidence to the complexity of the problem. [E.g., last paragraph of Sec 1.1]
4. The fact that seemingly related problems have a specific complexity is evidence for a given problem also to have this complexity. [E.g., second half of Sec 1.3]

I like Boaz's assertion (at the beginning of Sec 1.3) by which a conjecture is useful (or good) is it has led to significant progress in the field.

Now, to my critiques, which are actually disagreements wrt some (important) issues that are secondary to Boaz's article. I do not like the title and the end of the 1st paragraph, since these give the impression of a gap between proof systems and truth (in models). I think this is not the issue; the issue is rather giving some weight to unsound inferences rather than totally dismissing them, and the question is how exactly to go along in such a shaky terrain.

Likewise, as stated up-front, I'm noth enthusiastic (to say the least) of calling a widely held conjecture by the name ``law of nature'' (as other sciences may do). I am happy to belong to a field that carefully articulate, for each assertion, the quantifiers under which it holds. Indeed, one may warm against losing sign of the assertion due to the quantifiers, but that's different than suggesting that the latter be dropped (a suggestion Boaz does not make, but other sciences often do and Boaz's text may be read as advocating that practice).

I do not think that ``blessed (or cursed?) with many open problems'' is an accurate enough description of the state of TOC as compared with other sciences. The issue is not the number of open problems, but their positions within the field.

Typo on line 6 of page 3: $a_i$ should be $x_i$.

I found the beginning of the 1st paragraph of Sec 2.1 quite confusing, since it describes a hypothetical situation that we know not to hold (as indeed stated later). At the very least, I'd use here phrases that clearly indicate the situation (i.e., ``would be'' --> ``could have been'').

I don't understand why Levin's theory of average-case complexity (and its ramifications) is not even mentioned in Sec 2.3; in my opinion, the basic theory as well as some ramifications (see, e.g., Noam Livne's work (*)) conflict with some of the feelings expressed in Sec 2.3.

Indeed, this work is not well-known. If you cannot get the text from the journal, due permission issues, you may fetch Noam's thesis. (Btw, see Noam's discussion of the notion of a ``natural problem'')