Web of C-lief: conjectures vs. model assumptions vs. scientific beliefs

A sketch of the theoretical computer science Web of C-lief weaved by the non-contradiction spider.

In his 1951 paper on the “Two Dogmas of Empiricism”, W.V.O Quine introduced the Web of Belief as a metaphor for his holistic epistemology of scientific knowledge. With this metaphor, Quine aimed to give an alternative to the reductive atomising epistemology of the logical empiricists. For Quine, no “fact” is an island and no experiment can be focused in to resole just one hypothesis. Instead, each of our beliefs forms part of an interconnected web and when a new belief conflicts with an existing one then this is a signal for us to refine some belief. But this signal does not unambiguously single out a specific belief that we should refine. Just a set of beliefs that are incompatible with out new one, or that if refined could bring our belief system back into coherence. We then use alternative mechanisms like simplicity or minimality (or some aesthetic consideration) to choose which belief to update. Usually, we are more willing to give up beliefs that are peripheral to the web — that are connected to or change fewer other beliefs — than the beliefs that are central to our web.

In this post, I want to play with Quine’s web of belief metaphor in the context of science. This will force us to restrict it to specific domains instead of the grand theory that Quine intended. From this, I can then adapt the metaphor from belief in science to c-liefs in mathematics. This will let me discuss how complexity class seperation conjectures are structured in theoretical computer science and why this is fundamentally different from model assumptions in natural science.

So let’s start with a return to the relevant philosophy.

For Quine, the web of belief metaphor was part of a grand, sweeping theory. He was arguing against the analytic vs synthetic distinction globally. So his web contained all kinds of beliefs: personal beliefs; scientific hypothesis, beliefs, facts, and theories, mathematical conjectures and theorems; and even the rules of logic. In principle, any belief could be refined, but the latter ones — like math and logic — are often just too central to our web of belief to give up or refine. We would almost always give up the more peripheral beliefs over something like our central beliefs in the rules of logic. This grandiose view of the web of belief opens up Quine to sometimes pedantic seeming — but well placed and helpful — objections like Daniel Tippens’ argument for the incoherence of giving up the principle of non-contradiction.

But we don’t have to be as grandiose as Quine in our use of the web of belief metaphor. Instead of using the web of belief to demolish the analytic vs synthetic distinction, we could use it locally as a metaphor for how ‘facts’ hang together in some concrete (sub-)field of science. We can focus on some limited domain of knowledge. For example, we might talk about the web of belief in oncology — an interesting question: how does the web of belief of mathematical oncologists differ from the web of belief of clinical oncologists? — or evolutionary biology. Or we might restrict to even smaller settings — like the proceedings of a particular criminal trial. It would be a silly case if the prosecuting attorney launched an attack on the law of noncontradiction during an obstruction of justice case; or if a defence lawyer tried to challenge our belief in the identity of indistinguishables in an anti-trust case. Instead, in such settings we would focus on a limited local web of belief that has a certain number of auxiliary beliefs that are treated as unquestionable for the role of that particular discourse.

I want to think only about local webs of belief for two reasons. First, I find it more useful to how I make sense of science and math in my day-to-day work. Second, unlike Quine, I do want to use a rough practical distinction between types of beliefs and knowledge even if in some grand Quinian metaphysical theory they would just lay as far apart points on some continuum of web-centrality. In particular, in my day-to-day work, scientific beliefs and mathematical beliefs are fundamentally different. A theorem has a certainty of a different kind than a scientific fact. And even a conjecture feels different from a hypothesis.

I think that these limited local webs of belief can be useful for thinking about the role of conjectures in mathematics. Especially the role of complexity class separation conjectures in theoretical computer science. Let me call this special web as the Web of C-lief.

Theoretical computer science is an interesting position among branches of mathematics in that much of its bedrock rests on a series of interconnected conjectures — a web of c-lief. Most famous among these conjectures is the P vs NP problems or the conjecture that P != NP. But there are many similar complexity class separation conjectures like L or NL vs P, P vs PSPACE, or the polynomial hierarchy. More specialized complexity class seperations like the FP != PLS conecture (on which I build much of my work in algorithmic biology), or the related FP != PPAD conjecture (that powers algorithmic game theory). Plus there are much more speculative conjectures like the exponential time hypothesis or very endogenous and divisive ones like the unique games conjecture for hardness of approximation. Although for most of the core conjectures, people tend to share similar beliefs on the truth status, tending to lean in favour of conjecturing complexity class separations rather than conjecturing complexity class equivalences.

There is a rich web of interdependence and implication between these conjectures. This includes both implications like P != NP implies P != PSPACE, where both the condition and consequence are expected to be true. And hypothetical implications like L = P implies (by the space hierarchy theorem) that P != PSPACE, where most people don’t expect the condition to be true but do believe the consequence (i.e. most people that L != P != PSPACE).
All of these various implications are very clear and precise, much more so than the links in the scientific web of belief.
The links in the theoretical computer science web of c-lief have the certainty of theorems, but the nodes have only the certainty of scientific ‘facts’.

Thus, the web of c-lief provides a very formal and precise description of what we don’t know. More importantly, it also often includes information about why we don’t know.

For many of the most central conjectures in the web of c-lief, we not only know how they relate to many other results but we also know why our current proof techniques cannot possibly prove them. In other words, we have theorems that establish certain barriers to proofs. We know that a proposed proof of some of the central conjectures cannot have certain structural features that are shared by most proofs that we’ve found so far for other theorems in theoretical computer science. Concretely, we know that a proposed proof of P != NP (and some other closely related conjectures) must overcome relativization, natural proofs and algebrization barriers (or for a proof of P = NP, there are other barriers).

In other words, in the cstheory web of c-lief, unlike the scientific web of belief, we know very precisely what we don’t know, how it relates to other things that we don’t know, and in many cases even why we don’t know it. It is this explicitness, precision, and concreteness — rather than just the ‘c’ at the start of ‘conjecture’ — that prompts me to call these objects c-liefs.

In 2008, Tamar Gendler introduced the concept of an alief for a mental state corresponding to an automatic or habitual belief-like attitude. She is especially interested in aliefs that are in tension with a our explicit beliefs. For example, a person standing on a transparent balcony may believe that they are safe, but alieve that they are in danger. In other words, aliefs are more implicit and less transparent and less communicable than beliefs.

I want to follow the alphabet further — up to c-liefs. As I tried to sketch above, scientific beliefs are less explicit and less clearly connected and articulated than the c-liefs of mathematical conjectures. More importantly, even the best scientists don’t always keep good track of the conditional nature of their beliefs and forget to always be mindful of the ‘this is conditional knowledge’ flag attached to the beliefs. A competent mathematician, however, even if she is making a very long and complicated deduction from a conjecture or set of conjectures, is always aware that these statements are conditional on the as-of-yet unknown truth-value of those conjectures. She never forges the ‘this is conditional knowledge’ flag in the way that scientists sometimes do.

Thus, whereas a-liefs are less transparent and less clear or precise than beliefs, c-liefs are more transparent, more clear, and more precisely stated than beliefs. Whereas we might not know that we hold certain a-liefs and act on them as if they are facts without realizing their conditional nature; when we hold certain c-liefs, we are always explicit about remembering the ‘this is conditional knowledge’ flag and propagating that uncertainty through our deductions.

With our web of c-lief metaphor sketched, let us turn to the way theoretical computer scientists use this web. Since local webs are meant as a practical way of making sense of beliefs, rather than as a grand unified theory, this use question is central.

Already in my description of cstheory c-liefs, as I jumped between the language of problem, conjecture, and foundation, it is clear that complexity class separation conjectures play several roles in cstheory. In one way, as with much of mathematics, these conjectures are problems or precisely stated puzzles that computer scientists work to resolve. People want to prove that P != NP. They want to resolve central conjectures. There might even be some serious researchers working directly on the question. Although in most cases, due to the numerous barriers, people tend to go after more approachable conjectures in the periphery of web of c-lief with the hope that a few resolutions started there might eventually propagate to the centre of the web. This is similar to how scientists tend to design experiments to go after peripheral hypotheses in the scientific web of belief to slowly grow it.

But not all cstheorists work towards resolving the conjectures in the web of c-lief. Instead (or in addition), many cstheorists use the web of c-lief as bedrock for much of their work. For example, if you prove that some obscure problem you are trying to find a good algorithm for is NP-complete then you will stop searching for an efficient algorithm. Instead, you will try to restrict the problem to tractable subclass of instances or switch focus to approximation algorithms. When working in this mindset, you are not trying to resolve the P vs NP problem by establishing your new problem as NP-compete. Rather, you are using the web of c-lief to guide you towards new approaches to finding an algorithm for a now refined version of your problem. In this case, you are acting as if P != NP (or at least as if you won’t be the one to resolve P vs NP) to simplify your life and focus your work.

To make this very concrete and personal: when I prove that the NK-model with K > 1 is PLS-complete, I am not hoping to use this to resolve the FP vs PLS conjecture. Instead, I use our belief in FP != PLS to then make the scientific claim that computational complexity can be an ultimate constraint on evolution. The c-lief is a bedrock on which I build further scientific beliefs.

In this way, the complexity class separation conjectures seem to work like axioms or model assumptions. In fact, I was prompted to write this post by Karen Kommerce’s tweet comparing complexity class separation conjectures to (empirically unjustified) assumptions in economic models. I don’t think that this is a reasonable comparison. Hopefully this post has explained why. For me model assumptions and conjectures are different in much the same way as scientific facts and mathematical theorems.

The most obvious dissimilarity is in the levels of certainty. This is not general to all conjectures, but applies only to central c-liefs in theoretical computer science. As the old joke goes, if computer scientists used the same standards of proof as physicists then the P vs NP question would have been solved in the 70s. Experimentally, the question of non-existence of an efficient algorithm for an NP-complete problem has been tested much better than most physical ‘facts’. In this way, these central conjectures have a much more solid grounding than most model assumptions.

Second, and more general, is that model assumptions are seldom known precisely. They are often very implicit. Sometimes implicit to the point that we might not endorse them if they were made explicit. And a lot of good scientific and philosophical work can be done in uncovering model assumptions. In this way, they are the polar opposite of c-liefs. A conjecture is only a conjecture when it is stated precisely.

But even when we do state our model assumptions relatively precisely (i.e. as some formal modellers do), we are not making these statements to highlight our ignorance. Instead, we are stating the model assumption to get the conversation going. The conversation might be productive and enlightening even if the model assumptions are wrong. A conjecture highlights our ignorance and does not let us forget the conditional nature of all the results based on it. The web of c-lief also interconnects the dependencies between conjectures much more explicitly than any set of model assumptions than I am familiar with.

Finally, the context of use for cstheory conjectures versus most model assumptions is very different. In the case of economics and evolutionary biology, most models are heuristics. As such, the truth value of the assumption matters much less than the usefulness value of the overall model. This is part of the reason why economists are not particularly taken aback by the ‘but humans aren’t rational’ critique. The economist knowns that her assumptions are wrong, but that in itself doesn’t make her model not useful. To convince the economist, I would have to not only challenge her model’s assumption but then also provide an alternative better model. In the case of cstheory conjectures, however, when they are used in modelling it is more often for abstractions.