3

A useful exercise to answer the question could be to build a simple Turing machine $M$ (let's say one tape and one head) that recognizes your language. Such a TM could work directly on the input tape and be equipped with an extremely simple transition function: Read input If $($input $= 0$ $\lor$ input $= 1$$)$ $\implies$ Move R (right on the tape) Note ...


2

All that you know is that R is NP-hard. To show that R is NP-complete, you need to show that it is in NP. But that is not automatically true. As an example, let S be the question "Is there a path of cost at most l that visits every node of a graph G?" and R be the question, "What is the cheapest path that visits every node of a graph G?" These are ...


Only top voted, non community-wiki answers of a minimum length are eligible