# Redefining the Analytic/Synthetic Distinction in Terms of Computational Complexity

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?

• The main problem I see is that it as Kant wants the distinction to work for natural language expressions, the functions necessary for polynomial reduction are often not uniquely definable. Frege, Carnapp and Wittgenstein failed in their attempts to make a formal language that is able to formalise natural language without loss of meaning, i.e. express equivalently. Therefore, as useful as it might be in certain fields (i.e. logics, mathematics), it cannot account for all that Kant wanted and needed. Jan 2, 2017 at 20:48
• 'A triangle having 180 degrees seems less tautological than saying "An unmarried bachelor".' Why?
– user20153
Jan 2, 2017 at 22:58
• Prime Factoring is not NP Complete, it is in the "middle", harder than P, but not NP-Complete the way Boolean SAT or TSP are. Jan 3, 2017 at 7:37

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.

• For your first point of New Orleans being the largest city in Louisiana, I don't quite see how that is problematic. If I asked you (not some computer) to verify the truth validity of the claim "New Orleans is the largest city in Louisiana", you would probably find a list of all cities in Louisiana broken down by square footage, and simply find the biggest. Finding a less efficient algorithm for doing a process doesn't change the complexity class that the problem is in. The fact is that there exists an algorithm that runs in linear time which verifies this claim - hence abolishing ambiguity Jan 3, 2017 at 21:29
• Then, for the triangle point - the fact is that I could call a triangle "Shapesicle". It's true that the name would not be nearly as helpful as "Triangle", but in the spirit of de dicto modality, this is not binding to the thing itself. So, a triangles' 180 degree-ness doesn't feel nearly as necessarily true (that is, as tautological) as a bachelor's unmarried-ness. Jan 3, 2017 at 21:32
• I guess what I'm trying to get at is that Kant's analytic/synthetic distinction at its core seems to me to be about finding a distinction in kinds of knowledge. That is, some knowledge is immediately accessible, whereas other kinds are not. This distinction seems at least somewhat isomorphic (that is, in the ballpark of) different complexity classes. Some computable statements are more accessible than others. Jan 3, 2017 at 21:34
• You're conflating what a decision problem in computer science is with what verifying that a statement is true in philosophy is. The definition of an analytic statement is that to verify the truth or falsehood of the statement requires only knowing the definition of the words used. My point is that "New Orleans is the largest city in Louisiana" is a synthetic statement. It is not an analytic statement, but by your definition it would become an analytic statement because we could verify the information in linear time, given a look up table. That is completely out of line with the definition. Jan 3, 2017 at 21:53
• As for changing the word to “shapesicle,” yes, you could call a triangle a shapesicle, but you would mean a triangle, and if asked for the definition of shapesicle you would say “its a shape that has three sides and all of the angles add up to 180” so we would know by definition that a shapesicle has 180 sides. You’re saying that the distinction has to do with how accessible knowledge is, but that has absolutely nothing to do with the computational steps to solve a math problem. The accessibility has to do with definitions. Jan 3, 2017 at 21:53

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.)

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.)

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.