*David A. Tanzer, January 2021, in unit Language Complexity*

How complex is the English language? That’s a tough nut to crack. Here we’ll reframe the question in a more formal setting which is shared by computer science and linguistics: the theory of formal languages and their complexity. By the end, we’ll reach a technical understanding of what is meant by the famous conjecture P != NP.

To talk about the … Read more

*David A. Tanzer, January 2021, in unit Language Complexity. Cross-posted to the Azimuth Blog*.

**A simple view of languages**

How complex is the English language? The question has many dimensions and nuances. What does complexity mean, and how could it be measured? This a tough nut to crack, so in this post we’ll make a retrenchment and reconsider the question in a more formal setting — computer science.… Read more

*David A. Tanzer, January 30, 2021, in unit Language Complexity.* *Cross-posted to the* *Azimuth Blog.*

**Decision problems, decision procedures and complexity**

In Part 1, we introduced the formal idea of a language, as being just a set of sentences. Now let’s approach the topic of language complexity.

For any given language, there is an associated *decision problem*: given a candidate string of characters, determine whether or … Read more

*David A. Tanzer, February 7, 2021, in unit Language Complexity. Cross-posted to the Azimuth Blog.*

**A detailed measure of computational complexity**

In Part 2, we identified language complexity by how “difficult” it is for a program to decide if some given text is a sentence of the language — in other words, by the complexity of the decision problem for the language.

Note there may be many … Read more

*David A. Tanzer, February 8, 2021, in unit Language Complexity. Cross-posted to the Azimuth Blog.*

**Summarizing computational complexity**

In Part 3 we defined, for each program P, a detailed function P'(n) that gives the worst case number of steps that P must perform when given some input of size n. Now we want to summarize P into general classes, such as linear, quadratic, etc.

**What’s in a step?**… Read more

*David A. Tanzer, February 9, 2021, in unit Language Complexity.* *Cross-posted to the Azimuth Blog*.

**Big O analysis**

Recall our function $f(n)$ from Part 4, which gives the values 2, 13, 14, 25, 26, 37, …

Using ‘big O’ notation, we write $f(n) = O(n)$ to say that $f$ is linearly bounded.

This means that $f(n)$ will eventually become less than some linear function.

As we said, … Read more

*David A. Tanzer, February 10, 2021, in unit Language Complexity. Cross-posted to the Azimuth Blog.*

**Quadratic complexity**

In Part 5 we introduced big O notation for describing linear complexity. Now let’s look at a function with greater than linear complexity.

```
def square_length(text):
# compute the square of the length of text
# FIXME: not the most elegant or efficient approach
n = length(text)
counter = 0
for i
```

…

Read more
*David A. Tanzer, February 11, 2021, in unit Language Complexity. Cross-posted to the Azimuth Blog.*

**Higher complexity classes**

In Part 6, we saw a program with quadratic complexity. The collection of all languages that can be decided in $O(n^k)$ time for some $k$ is called P, for polynomial time complexity.

Now let’s consider languages that appear to require time that is exponential in the size of the input, … Read more