8
$\begingroup$

I want to ask exactly what is the relationship between problems and languages. We know that the set of all languages uncountable. Is the set of problems also uncountable? Can every problem be defined by a language? Can a language solve more than one problem and vice versa? Is there one-to-one correspondence between problem and languages?

$\endgroup$
11
$\begingroup$

Decision problems and languages are just the two sides of the same coin: every problem can be rephrased as the membership problem of some language. The problem of, say, determining whether a number is prime is exactly the membership problem of the language of prime numbers.

Formally, a language is a set of finite strings over some fixed finite alphabet (sometimes, the strings are allowed to be infinite; that's a different but related scenario). Problems that aren't directly questions about strings will need to be encoded as strings so, for example, it would have been more precise to write the last sentence of the previous paragraph as, "If we fix an alphabet and an encoding of natural numbers as strings over that alphabet, the problem of, say, determining whether a number is prime is exactly the membership problem of the language of strings that encode prime numbers."

To quickly run through your subquestions,

We know that the set of all languages uncountable. Is the set of problems also uncountable?

Yes, since problems and languages are essentially the same thing.

Can every problem be defined by a language?

Decision problems, yes. Optimization problems (what's the smallest X with property Y) and counting problems (how many X's have property Y) can be rephrased as decision problems (is the Z the smallest X with property Y?; are there N X's with property Y?), though that's usually not the most natural way of treating them.

Can a language solve more than one problem and vice versa?

Yes and yes, because you have to use encodings to translate between problems and langauges. For example, the languages $\{10,11,101,111,1011,\dots\}$ and $\{2,3,5,7,11, \dots\}$ both encode the primality problem (in binary and decimal, respectively). Conversely, though perhaps a little artificially, the language $\{0, 10, 110, 1110, \dots\}$ encodes the problem of determining whether a binary number is of the form $2^k-2$ for some $k$ and the problem of determining whether a string of 1's and 0's has exactly one 0, which is its final character. (Perhaps somebody can come up with a better example of a language that naturally encodes two problems without one being such a trivial rephrasing of the other.)

Is there one-to-one correspondence between problem and languages?

No, since this question is just the complement of the previous one. :-)

$\endgroup$
  • 1
    $\begingroup$ what can u say about undecidable and unsolvable problems . does we can define them by a language if not then how every problem can be defined by a language. $\endgroup$ – Ravi Singh Aug 15 '15 at 19:49
  • 2
    $\begingroup$ Yes, undecidable problems also correspond to languages. For example, the halting problem corresponds to the language of strings that encode a Turing machine $M$ and an input $x$ such that $M$ halts when given input $x$. $\endgroup$ – David Richerby Aug 15 '15 at 20:16

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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