(c) Consider the hierarchy of complexity classes: P CNP, coNP C EXP C [12 marks] DEC C R.E. C LANG, where DEC are the decidable sets, R.E. are the recognisable sets, and LANG is the class of all sets of strings. Place each of the following sets, and its complement, in the smallest complexity class that contains the set (e.g. write: set A is in DEC and A is in R.E.) i. CLIQUE ii. ATM iii. S = {(M): M is a TM that accepts exactly five strings } iv. T = {(M): M is a TM s.t. M(1) = accept} v. U = {(M): M is a TM s.t. M(1) [20] = accept vi. V = {1 {0,1}* : starts with 1 } (c) Consider the hierarchy of complexity classes: P CNP, coNP C EXP C [12 marks] DEC C R.E. C LANG, where DEC are the decidable sets, R.E. are the recognisable sets, and LANG is the class of all sets of strings. Place each of the following sets, and its complement, in the smallest complexity class that contains the set (e.g. write: set A is in DEC and A is in R.E.) i. CLIQUE ii. ATM iii. S = {(M): M is a TM that accepts exactly five strings } iv. T = {(M): M is a TM s.t. M(1) = accept} v. U = {(M): M is a TM s.t. M(1) [20] = accept vi. V = {1 {0,1}* : starts with 1 }