In a lot of the online explanation of complexity theory, the author proposes the following.

"The definition associated with complexity theory (e.g., definition of NP) is phrased in terms of language $L$ and Turing Machine $M$.

But we can think of Turing Machines as algorithms, and Language as problems.

So instead of thinking in terms of languages and Turing machines, we can instead ask the question whether my algorithm decide/verify a solution exists for a given problem."

Is there the correct way of thinking about complexity theory, i.e., substitute language with problems and Turing machine with algorithms? Is there any major looseness in thinking this way?

I guess the problem for me is that I don't see the clear mapping between these concepts, i.e., a function that transforms language into problems, etc.



Your Answer

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

Browse other questions tagged or ask your own question.