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 problemOn 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 $<=$ L2Can 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
How does language relate to problem in complexity theory?
complexity theory
A (decision) problem is a predicate on strings (that is, a property of strings) that can be either TRUE or FALSE; the problem is to decide whether a string satisfies the predicate (that is, has the property). We represent this predicate as the set of TRUE strings (that is, strings satisfying the property). A language is a set of strings. Thus the denotations of problem and language are the same  they are both sets of strings  and they can be used interchangeably. But semantically we use problem when our set of strings comes from a predicate, and language in other cases.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.