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 

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