Question $3$

Fill the table as True of False for each of the following. Do not give explanations.

a$)$ A TM can compute anything a desktop PC can, although it might take more time.

b$)$ Every Turing$-$decidable language is also Turing$-$recognizable.

c$)4n^2=O(n)$

d$)$ The various sorting algorithms $($e$.$g$.,$ bubblesort, heapsort$)$ are in NP$.$

e$)$ The class of regular languages is closed under union.

$)$ A Push$-$Down Automata can compute things that a TM cannot compute.

g$)nlogn=O(n^2)$

h$)$ You cannot build a DFA to recognize $\{0^{500}{1}^{10000}{1}^{1000}{0}^{200}\}.$

i$)$ A regular language $L$ may not be context$-$free.

j$)$ From the complexity perspective, multi$-$tape Turing machines are equal to single$-$tape TM$.$

$\backslash$table$[[$Question$,$True$/$False$],[$A$,],[$B$,],[$C$,],[$D$,],[$E$,],[$F$,],[$G$,],[$H$,],[$I$,],[$I$,]]$