1
$\begingroup$

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

$\endgroup$
0

1 Answer 1

1
$\begingroup$

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.

$\endgroup$
3
  • $\begingroup$ Very intriguing answer, but can you provide a simple example on what a problem may be phrase as, and what a string looks like? I'm still not comfortable with a problem taking in a string, is a problem in this case the same as a function and string the same as the argument? $\endgroup$
    – Fraïssé
    Commented Dec 3, 2014 at 3:57
  • $\begingroup$ A problem doesn't take in anything. The problem is to decide, given a string, whether it belongs to a certain language. It is an algorithm for solving the problem that takes in a string. $\endgroup$ Commented Dec 3, 2014 at 10:01
  • $\begingroup$ You may want to add your thoughts to our reference question. $\endgroup$
    – Raphael
    Commented Dec 3, 2014 at 11:28

Not the answer you're looking for? Browse other questions tagged or ask your own question.