Redefining the Analytic/Synthetic Distinction in Terms of Computational Complexity

Question

I've been reading Kant for the first time and encountered Quine's objections to the analytic/synthetic distinction and am want to agree that they feel a little obscure in their definitions. That is, Kant's examples I don't know quite spell out a clear obvious distinction. For example, a triangle having 180 degrees might be analytic in that it's always been part of the construction of the idea of a triangle, even if it's not immediately obvious to us.

However, I think there's probably something to the idea that there's a distinction between different types of knowledge. A triangle having 180 degrees seems less tautological than saying "An unmarried bachelor".

So, I was thinking of trying to define this distinction in terms of different classes of problems - a field best expressed with computational complexity. So, for example, the fact that the prime factors of 45 are 3, 3 and 5 would be a synthetic fact because the problem is NP-Complete. The fact that 2 + 2 = 4 would be analytic though because addition runs in linear time.

Is this a good or interesting distinction? Does this do the work that Kant needs it to do?

Answer 1

It's very hard to understand what a connection between the analytic/synthetic distinction and computational complexity could mean.

As an example objection to the idea: if you are saying that synthetic statements are somehow equivalent to an NP-complete question, how would you handle the statement:

New Orleans is the largest city in Louisiana.

What is NP-complete about that statement? Does an algorithm that decides the answer to that question run in NP-complete time? How would you go about verifying any synthetic statement in relation to a specific complexity class? An issue that you will run into many times when trying to formulate this comparison is how you choose what complexity class fits each description. Let's say that we verify that synthetic statement by looking up a table of Louisianan cities and their area. If it is sorted by smallest to largest and we could process one entry per second, then verifying that statement would run in linear time proportional to the size of the list. However, what if we verify it another way? What if we went to Louisiana and measured all of the cities by hand? There is a chance that the algorithm we use to measure would be of a different complexity class than the one we used on the list. This is not good if you are trying to associate synthetic statements with complexity classes. How are you going to prove the hardness of statements such as:

Susanne went shopping today.

It feels as though the idea of identifying this distinction with complexity classes (especially classes that haven't been proven to be distinct yet (although to be fair, of course most sane people believe its true)) is very arbitrary and unfounded.

Also, I think that your example of triangles might be a little misguided. You're right, the reason the statement

The angles making a triangle add up to 180 degrees

is analytic is because that is how the word is defined; however, think of the etymology of the word "triangle." We have two morphemes, "tri" and "angle," and it is a matter of fact that you cannot have three angles connecting three lines that do not add up to 180 degrees (in Euclidean space, at least). So really, that statement is on par with the self evidence of the sentence

All bachelors are unmarried.

To address the computational complexity idea: why would the suggested classes of complexity relate to analytic and synthetic statements?

The prime factors of 45 are 5, 3, and 3

is an analytic statement. (Also, prime factorization isn't even an NP-complete problem!) It only requires the understanding of what a prime factor is. If you have access to the definition of the word you would be able to figure those numbers out while sitting with your eyes closed in your arm chair. It might take more time for you to figure it out than if you were trying to add 2 and 2, but the only difference in these two examples is time. Both of these statements are analytic, whether or not one takes more time to verify than the other.

One last thing to note. If we decided to adopt this redefinition and we had the sentence:

All professors are smart

which is a synthetic statement given the canonical definition, and we had an algorithm that decides that statement in NP-complete time we would label it synthetic. What would happen if in two years someone finds an algorithm that decides that question in polynominal time? Would we then discover that that sentence is actually analytic, we just didn't know? In that sense, we could use the example of listing information and then verifying a statement would just become scanning a list, so all statements would become analytic because that would be a linear time algorithm. Discovering a sentence is analytic instead of synthetic by going out and doing something in the world is completely antithetical to the idea of an analytic statement.

Answer 2

I think it's crucial to see here that all computational problems whether be in any classified complexity are always analytical. Well defined mathematical problems (that can be computed) need to be tautological in the sense linguistic expressions are, just as the provided example of bachelors. Whether it be prime factoring or addition their algorithms are analytical as they are derived from axioms of a mathematical foundation.

You are raising a completely different distinction with complexities and in my opinion it's not possible to reduce them to the analytic/synthetic distinction. See your own example:

For example, a triangle having 180 degrees might be analytic in that it's always been part of the construction of the idea of a triangle, even if it's not immediately obvious to us.

What you are making a distinction of is the immadiately part, because complexity is mostly a scaling by time. Complexity classes of problems are not different in analiticity, you could say that all mathematical statements ought to be obvious to us if they are true. A synthetic mathematical statement should be actually a meta-mathematical statement, because to introduce new types and meaning into your framework and give room for synthetic truths you need to rework the foundations as well.

In summary, computational complexity is a matter of the scaling of time while the distinction what Kant and Quine speaks of is the scaling of meaning.

(Also on a side note, I'd suggest you to look into the work of Whitehead and Russel's Principia Mathematica as they were trying to broaden the scope of analyticity into language itself, something I feel like that you are trying to do so with this question.)

Answer 3

I think you framed the question well when you asked, "Does this do the work that Kant needs it to do?" However, when you speak of problems being NP-Complete, it sounds like you're perceiving it as a matter of how obvious it is or how easily its truth can be discovered by reason, and I think that misses the point with respect to what Kant actually needed the distinction to do.

One of the things that he needed to do is in consonance with what Quine is asserting: Kant needed the necessity of analytic judgements to be rooted in the tautology of definition as established by convention or agreement. As Quine said, "Functionally a definition is not a premise to theory, but a license for rewriting theory by putting definiens for definiendum or vice versa." ("Truth by Convention") I've already addressed that in more detail in another post.

Another thing he needed to do was to maintain that all synthetic judgements actually assert something, i.e. they must contribute something to the knowledge about the subject. For example, we might propose the following two definitions:

• ∀x[Dx ↔ Ax]
• ∀x[Ex ↔ Ax & Bx]

Given that they are definitions we can assert that they are necessarily true by convention, and they are also vacuous because, being definitions, they contribute nothing to our knowledge, as Quine insists.

It might be argued that they both have the property A in common, so the second definition makes a substantial claim. However, that's not the case at all because, as a definition, it doesn't assert that there is anything that has both the properties A and B, nor does it assert that having property A implies having property B. It only establishes that, by convention, if there should be something that has both properties, then we may refer to it as E. In virtue of that alone is it an analytic proposition.

On the other hand, given the first definition of D, if we were later to assert that ∀x[Dx → Bx], this would be adding to the definition and would thus be a synthetic judgement. We could also conclude that ∀x[Dx → Ax & Bx], which would also be synthetic, because it was not established by convention but by means of another synthetic judgement. What's important to notice here is that ∀x[Dx → Ax & Bx] has a form almost exactly the same as the second definition, but one is synthetic and the other analytic. The difference has nothing to do with content but with how their truth value is established.

Therefore, it can be seen that distinction between analytic and synthetic cannot be discovered on the basis of some empirical or analytical test; rather, it has to be determined according to the conventions of language that we choose to use. Synthetic judgements are those whose truth value depend on something other that mere convention alone.

Concerning mathematics, I believe that Kant was probably mistaken that some propositions of arithmetic are synthetic. However, I believe that he was correct concerning some geometric ones. The difficulty in deciding the question has to do with determining exactly what it means to assert that the forms of intuition can be characterized by a particular system of geometry. However, given that some geometric primitives cannot be defined in a way that is non-circular, I believe that they serve as a basis for certain propositions whose true value can't be attributed to either convention or empirical evidence (the forms of intuition being non-empirical in nature).

(The point of mentioning my opinions about mathematics is not to convince you one way or the other; rather, it's intended to illustrate how the analytic-synthetic distinction might be applied to Kantian questions.)

Answer 4

If I understand you correctly you are thinking along these lines:

• If a problem is in P, solving it is easy and therefore there is no added information in solving it. Therefore the problem is Analytic.
• If a problem is NP Complete or NP Hard, solving it is not trivial. Someone who does solve it is therefore bringing additional information to the table by solving it, including possibly knowledge resulting from experience and training. The problem is therefore synthetic.

Personally I do find this distinction interesting, but I seem to be in a minority. See these posts and the responses within: Do limitations on computability and computational resources have any consequences for epistemology? and Computational intractability and reductionism?.

The closest concept to the distinction you describe that I have found in the literature is the concept of of strict finitism or ultra-finitism: numbers and formulas which are too large to be computed efficiently are in a different epistemic category than numbers and formulas that can be efficiently computed, e.g. (11^65)! doesn't designate the same type of entity that 3 or 34561738457243 do. (see here, here, and here)

Kant himself might not be sympathetic to this distinction: whether evaluating 5+7 or (11^65)!, from his point of view the mind is still brining additional information to the table, and hence both are synthetic. Quine, belonging to the tradition of American Pragmatism, would find this distinction between statements that can be evaluated in practice and statements that can only be evaluated in theory much more appealing though.

Scott Aaronson has an interesting paper on the topic.