Tessellate S.T.E.M.S. (2019) - Computer Science - College - Set 4 - Objective Problem 1

Which of the following problems is NOT NP -Hard? You may assume P $\neq$ NP .

• A) Given a Turing machine $M$ and a string $x$ , does $M$ accept the string $x$ ?
• B) Given a pushdown automaton $M$ and a string $x$ , does $M$ accept the string $x$ ?
• C) Given a graph, is it possible to colour the graph using only 4 colours in such a way that no two adjacent vertices have the same colour?
• D) Given a graph, is it possible to colour the graph using only 3 colours in such a way that no two adjacent vertices have the same colour?

This problem is a part of Tessellate S.T.E.M.S (2019)