>>11700542>solve this brainletsDude this is an easy as shit problem, don’t be the reason this board makes fun of CS majors.
If L is in P, then there is some Turing machine M that decides it in DTIME(poly(n)) where n is the size of the input bits. To decide L5, devise machine M’ to do a simple iterated check that the input’s first 5 characters are nonblank tape symbols, which is a constant check. Then have M’ simulate M on the input if this is the case. The total runtime is polynomial, so obviously L5 is in P.
If L is in NP, there is some polynomially sized certificate such that M can verify every YES instance in polynomial time. Thus, to construct a verifier L5, we can basically use the same verifier M except we do the same size >= 5 check as above, which is constant time. Then if the input is in L, there is an advice string, and if not, there should be no advice string, and thus we can see we can decide L5 in NP given L is in NP.
