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