0
$\begingroup$

So I started to learn theory of computation and in the class we talk about languages and many-one $\leq_m$ reductions. e.g if $A \leq_m B $ then if $x \in A \implies f(x) \in B$

We say that different languages may be reducible to one another. I am curious how this relates to reduction that we have done in algorithms class. E.g $SAT \leq 3CNF$ or $Hamiltonian Cycle \leq TSP $

Are these problems considered to be languages??? I am confused because we are talking about some similar things as reductions, but now we talk about languages over the alphabet $\sum$ and not NP problems and I am curious if NP problems are actually languages as well.

$\endgroup$
0
$\begingroup$

Yes, the problems are languages in a certain sense. Take SAT, as an example. The satisfiability problem, SAT, is, given a formula $\varphi$, is $\varphi$ satisfiable? (Of course, this has to be asked with respect to some specific satisfiability relation.) The corresponding language is then $SAT = \{\varphi \mid \varphi \text{ is satisfiable}\}$, and the decision problem is, given $\varphi$, is $\varphi \in SAT$?

As a slightly technical addendum, we often have to translate the problem into the language of whatever formalism we are working in to talk about computation. If we are talking about Turing machines, for example, this means that we need to encode $\varphi$ as an input to the Turing machine. This encoding is sometimes denoted by $\langle \varphi \rangle$, so the language really becomes $$SAT = \{\langle \varphi \rangle \mid \varphi \text{ is satisfiable}\}.$$

$\endgroup$

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.