Yes, both $P$ and $NP$ are closed under union, intersection, concatenation and Kleene closure!
I will be demonstrating all of these, but instead of using Turing Machines, I will be using Python functions. It is important to note that Python (like all modern programming languages) is Turing Complete, and that for any TM you give me, I can write a python program for it and for any Python program you give me, I can make a Turing Machine for it.
Also, instead of talking about languages, which are sets of words, I will be talking about functions.
So, if we have a language $L \in P$, I will be considering a function $\rm fn\_L()$ which takes an input string $s$, and returns a boolean indicating whether $s \in L$ or not. Also, since $L \in P$, I will consider that the function $\rm fn\_L()$ takes polynomial time in the length of the input $s$. Similarly, if $L2 \in NP$, the function $\rm fn\_L2()$ takes polynomial time in the length of the input $s$, but also uses non-determinism.
What does it mean for a function to use non-determinism? It means that if at any point the function needed to decide one out of $k$ different paths to take, it would not have to explore all the $k$ paths. It would magically know the correct path, and simply take that correct path. Note that non-determinism is not the same as parallel computation. In parallel computation, you take all possible paths parallely. In non-determinism, you only take 1 path, but you can magically know which correct path you need to take.
Union and intersection are simple.
Given $\rm fn\_L1()$ and $\rm fn\_L2()$, I can simple construct intersection and union as following.
def fn_L1(input_string): ...
def fn_L2(input_string): ...
def fn_L1_intersection_L2(input_string):
return fn_L1(input_string) and fn_L2(input_string)
def fn_L1_union_L2(input_string):
return fn_L1(input_string) or fn_L2(input_string)
Now, how much time do these new functions take? They call both $\rm fn\_L1$ and $\rm fn\_L2$, and also do a constant time computation (the boolean or/and). So, the complexity of both the union and intersection functions are $O \Bigl (fn\_L1(n) + fn\_L2(n) \Bigr)$.
If both $fn\_L1$ and $fn\_L2$ take polynomial time and don't use non-determinism, then our union and intersection also takes polynomial time and don't use non-determinism.
Similarly, If both $fn\_L1$ and $fn\_L2$ take polynomial time and don't use non-determinism, then our union and intersection also takes polynomial time and don't uses non-determinism (by calling those oher functions).
So both $P$ and $NP$ are closed under union and intersection.
Concatenation isn't too hard either.
It can be constructed as follows:
def fn_L1(input_string): ...
def fn_L2(input_string): ...
def fn_L1_concatenate_L2(input_string):
# split the input string into two parts: head and tail.
# For us to accept the input_string, the head must be
# accepted by fn_L1, and the tail must be accepted by fn_L2.
# but we don't know the location to split the input_string at,
# so we can simply try all possible splits
for index in range(len(input_string)):
head, tail = input_string[:index], input_string[index:]
if fn_L1(head) and fn_L2(tail):
return True # accepted
# we've tried all possible splits and didn't find any
# working split. So this input_string cannot be accepted
return False
In the best case, our very first split will work. In the worst case, we will have to try all possible splits.
Thus, our worst case complexity is $O(n) \times O \Bigl (fn\_L1(n) + fn\_L2(n) \Bigr)$
We can see that in the worst case, we're only increasing our complexity by a factor of $O(n)$, which is a polynomial increase. Thus, we're still not breaking out of our complexity class.
So, both $P$ and $NP$ are again closed under concatenation.
Note: for the $L_1, L_2 \in NP$ case, we don't actually need to add the polynomial complexity, as by using non-determinism, we can magically know the correct way to split our string in $O(1)$ time and choose that split. Example code which makes use of non-determinism:
def fn_L1_concatenate_L2(input_string):
# use non-determinism to decide where to split
index = non_deterministic_magic(input_string)
head, tail = input_string[:index], input_string[index:]
if fn_L1(head) and fn_L2(tail):
return True
else:
return False
The Kleene closure is the trickiest one, but still doable.
Let's consider an input string $s = w_1, w_2, \ldots w_k, w_{k+1}, \ldots w_n$.
Now, if $(\text{head} = w_1, \ldots w_k) \in L$ and $(\text{tail} = w_{k+1}, \ldots, w_n) \in L^*$, then $s \in L^*$.
However, we don't know what the value for $k$ is, so we need to do something about that.
If we're talking about $L \in NP$, we have the freedom to use non-deterministic magic. So we will say that we magically find out in $O(1)$ time what the correct value of $k$ is. The algorithm is then simple.
def fn_L(input_string): ...
def fn_L_star(input_string):
# base case
if input_string == '':
return True
# recursive case
# use non-determinism to decide where to split
index = non_deterministic_magic(input_string)
head, tail = input_string[:index], input_string[index:]
if fn_L(head) and fn_L_star(tail):
return True
else:
return False
So $NP$ is closed under Kleene star. What about $P$ though? We can't use our non-deterministic magic for $P$ and we still need to decide where to split. We can't simply try our all possible splits, since that will increase our complexity to an exponential amount! So can we still do it?
Surely, by using dynamic programming!
from functools import lru_cache
def fn_L(input_string): ...
@lru_cache(None)
def fn_L_star(input_string):
# base case
if input_string == '':
return True
# recursive case
# try out all possible splits
for index in range(len(input_string)):
head, tail = input_string[:index], input_string[index:]
if fn_L(head) and fn_L_star(tail):
return True
# none of the possible splits worked
return False
Our recursion tries out all possible splits, which should make our complexity exponential, but since the problem has overlapping substructure and we're caching our results, the complexity only increases by a polynomial amount ($n^2$ in this case).
Thus, $P$ is also closed under Kleene closure!
