# How does “language” relate to “problem” in complexity theory? [duplicate]

I am looking up the meaning of reduction in complexity theory:

On Wikipedia it says: reduction is an algorithm for transforming one problem into another problem

On the Princeton's notes on NP-Completeness, it says: reduction is whereby given all x $\in$ language L1, for instance f(x) $\in$ L2, apply decision algorithm to f(x), then L1 $<=$ L2

Can someone make clear how a language (which is just a bunch of numbers) relates to a problem? If they are used interchangeably, can someone show how does I can conceptualize a language as a problem?

Thanks

## marked as duplicate by Raphael♦Dec 3 '14 at 11:27

Here is an example. The NP-complete problem CLIQUE is the set of all pairs $(G,k)$ such that $G$ is a graph that has a $k$-clique. As stated, this is not really a set of strings, but rather a set of pairs $(G,k)$. But when we say the set of all pairs $(G,k)$ we really have some encoding in mind. For example, we can encode a graph $G$ as a list of edges, where the vertices are indexed by numbers, in the format $((i_1,j_1),\ldots,(i_\ell,j_\ell))$. For example, the following is an encoding of a triangle $((1,2),(1,3),(2,3))$. Under this encoding, the language CLIQUE contains the string $(((1,2),(1,3),(2,3)),3)$ but not the string $(((1,2),(1,3),(2,3)),4)$ nor the string $()()($, for example. Another issue that comes up when we talk about strings is: strings over what alphabet. In this case, our strings are over the alphabet $(),0123456789$; but since everything can be encoded in binary, we typically imagine such binary encoding of our strings.
CLIQUE is a predicate on pairs $(G,k)$ that holds if $G$ is a graph containing a $k$-clique. It is also a property of pairs $(G,k)$, that of $G$ having a $k$-clique. The corresponding language (which we identify with the CLIQUE problem) consists of all strings encoding (in a fixed way) pairs of graphs $(G,k)$ such that $G$ has a $k$-clique. The corresponding decision problem (which we identify with the language of all accepted instances) is to decide, given a pair $(G,k)$, whether $G$ contains a $k$-clique.