# Why use languages in Complexity theory

I'm just starting to get into the theory of computation, which studies what can be computed, how quickly, using how much memory and with which computational model.

I have a pretty basic question, but am really hoping some of you guys can help me understand the concept behind it:

Why is everything centered around the notion and definition of LANGUAGES (i.e. regular languages and context free languages)? And how do these relate and describe the complexity of an algorithm and the possible computational models for solving them?

I read these sort of related questions:

but still don't have an answer to my doubts, since they provide a practical justification of why they are important (which I do understand) but don't help me understand why complexity theory is based upon them.

• Isn't this covered by our reference questions?
– Raphael
Apr 14, 2014 at 18:11
• @Raphael - Thanks for pointing me out to that question, it's a great reference! I am reading through it right now, but at the moment I believe this could be an addendum to the question cs.stackexchange.com/questions/13669/…. It doesn't seem to me that it is answered already, please let me know if you thin otherwise Apr 14, 2014 at 18:19
• A language is just a set of finite length strings, which is the same as a function that maps finite strings to 1 or 0. So you are really asking "why is so much of complexity theory about decision problems" and the answer is that it's the simplest (nontrivial) kind of computational tasks, and often more complicated computational tasks can be reduced to decision problems. Apr 15, 2014 at 0:08

It's because languages are the best (only?) way we have of formalizing the concept of a "problem."

An algorithm (Turing Machine) has performance, which we express via big-O complexity. A problem (language) belongs to a complexity class. These are usually defined by existence: if there exists a machine accepting a language $L$ which runs in given performance (space or time), then the language belongs to the corresponding complexity class.

There's a few reasons for this. First is that languages are platform independent. You're not worrying about whether an integer is 32 or 64 bits, or whether floating point operations run in parallel with other operations. These things give performance speedup at the micro-level, but complexity analysis is interested in the macro level. As you scale from 100 to $10^6$ to $10^9$ to $10^{12}$ inputs, how does the algorithm performance change? Does it go from using 1 million tape cells to 1 billion, or from 1 million to more cells than there are atoms in the universe?

The second is that languages are just a nice abstraction for data. You need something you can do proofs about, something you can model formally. Encoding your input and output as a string mean that you're now dealing not with bits in memory, but with mathematical objects with specific properties. You can reason about them and prove proofs about them in a formal, and very simple sense.

Complexity theory tends to be focused on decision problems because they end up being difficult. When the decision version of travelling salesman is NP-complete (i.e. is there a tour shorter than length $k$), then obviously finding the shortest path is harder. There isn't as much focus on function/optimization problems because there's still a lot of open questions and unsolved problems about the simpler decision problems.

I guess here's my challenge to you: find way to mathematically describe problems that isn't languages. I don't know if languages are special, but I think they're the simplest tool we've got, the easiest one to deal with.

• Languages certainly aren't the only way of formulating problems. For example, you could formalize something like chromatic number as a function from graphs to natural numbers. And, actually, there's quite a lot of work on function and optimization problems. Apr 14, 2014 at 17:44
• True, but how would you deal with the complexity of calculating the chromatic number without some concept of a language or machine? Apr 14, 2014 at 17:51
• Thanks for your answer, I get your point. However I still have 2 questions: 1) won't the fact that we are using languages affect the results about complexity or decidability of a problem? i.e. could a problem be solvable in floating point arithmetic but not in integer arithmetic (i.e. integer programming)? 2) How do we do this mapping from any kind of data to a unique language that describes them all (since we want to evaluate complexity of a problem and abstract from the specific input)? Thanks again! Apr 14, 2014 at 18:10
• @jmite You need a machine, yes, but not necessarily a language.
– Raphael
Apr 14, 2014 at 18:12
• @Raphael many complexity classes that are usually defined in terms of running time of machines can be characterized in terms of descriptive complexity. Apr 15, 2014 at 0:04

1. There is more to complexity theory than languages, for example function classes, arithmetic complexity, and the subareas of approximation algorithms and inapproximability.

2. Historical reasons: one of the basic papers in computability theory was discussing Hilbert's Entscheidungsproblem (a form of the halting problem).

Unfortunately I don't know much about the latter, but let me expand on the former.

## Complexity beyond languages

Every computational complexity class comes with an associated function class. For example, the class P of all problems decidable in polynomial time is associated with FP, the class of all functions computable in polynomial time. FP is important since it is used to define NP-hardness: a language $L$ is NP-hard if for every language $M$ in NP there is a function $f_M$ in FP such that $x \in M$ iff $f_M(x) \in L$. Another complexity class of functions, #P, is related to the so-called polynomial hierarchy via Toda's theorem.

Arithmetic circuit complexity (or algebraic complexity theory) deals with the complexity of computing various polynomials. Important complexity classes here are VP and VNP, and geometric complexity theory is an important project attempting to separate VP and VNP (and later P and NP) using algebraic geometry and representation theory.

Another important example of algebraic complexity is fast matrix multiplication. Here the basic question is how fast can we multiply two matrices? Similar questions ask how fast we can multiply integers, how fast can we test integers for primality (this is a decision problem!) and how fast can we factor integers.

Convex optimization deals with optimization problems that can be solved (or almost solved) efficiently. Examples are linear programming and semidefinite programming, both of which have efficient algorithms. Here we are interested both in the optimum and in the optimal solution itself. Since there is often more than one optimal solution, computing an optimal solution is not well represented as a decision problem.

Approximability is the area that studies how good an approximation we can get for an optimization problem in polynomial time. Consider for example the classical problem of Set Cover: given a collection of sets, how many of them do we need to cover the entire universe? Finding the optimal number is NP-hard, but perhaps it is possible to compute an approximation? Approximation algorithms is the subarea studying algorithms for computing approximations, while inapproximability studies limits of approximation algorithms. In the particular case of Set Cover, we have an algorithm giving a $\ln n$ approximation (the greedy algorithm), and it is NP-hard to do any better.

Let's look at this question from the perspective of category theory. The decision problems (or languages) would then correspond to the objects of a category, and the allowed reductions between two problems would correspond to the morphisms (arrows) of a category.

Talking about languages has the advantage that equivalence of languages is well defined (namely by extensional equality). Two unrelated problems might lead to the same language, and then we are allowed to consider them as equivalent. If we would want to talk about isomorphic problems instead, we would have to define the allowed morphisms between two problems. But the allowed morphisms depend on the actual complexity class under consideration, which makes this approach less suitable for comparing different complexity classes.

The notion of isomorphic problems will normally be coarser than the notion of equivalent languages, i.e. two problems can be isomorphic, even if their associated languages are not equivalent. What is worse is that there are often different reasonable notions for the allowed morphisms, which only agree with respect to the allowed isomorphisms. Focusing on languages allows to postpone such problems until we feel like talking about some different reasonable notions of reduction (like Karp reduction vs. Cook reduction).

• This doesn't seem to answer the question. One could still talk about morphisms between problems whatever one uses as the objects in the corresponding category. Apr 15, 2014 at 7:43
• @DavidRicherby The point I wanted to bring across is that nailing down the appropriate morphisms is more challenging than nailing down the appropriate objects (=languages). (Especially since there is normally more than one appropriate notion of morphisms.) Without morphisms, you can't talk about isomorphic problems (or algorithms). However, languages give you a way to still talk about equivalence of problems. Perhaps I didn't explain this properly, but (for me) this is a good reason for "using languages in complexity theory". Apr 15, 2014 at 8:37