Is DTIME(n) closed under concat? star? of course not but...
Computational Complexity 2018-04-16
(STOC 2018 will offer child care for the first time. I was emailed the following and asked to
pass it on:
We are pleased to announce that we will provide pooled, subsidized
child care at STOC 2018. The cost will be $40 per day per child for
regular conference attendees, and $20 per day per child for students.
For more detailed information, including how to register for STOC 2018
childcare, see http://acm-stoc.org/stoc2018/childcare.html
Ilias Diakonikolas and David Kempe (local arrangements chairs)
I tell my class that poly time is nice mathematically since its closed under lots of operations including
concat and *. That is:
L1 , L2 ∈ P implies L1 L2 ∈ P.
unlike DTIME(n) which, as you can see, is NOT closed under concat! After all, the proof that P is closed under concat uses that if p(n) is a poly then np(n) is a poly which does not hold for linear time. If p(n) is O(n) then np(n) is NOT necc O(n).
But--- thats not a proof that DTIME(n) is not closed under concat! Thats just the observation that the argument for P being closed under concat does not extend to DTIME(n). Perhaps some other argument does.
I do not believe that. I believe there exists L1 , L2 ∈ DTIME(n) such that L1 L2 is not in DTIME(n).
I have not been able to prove this. In fact, the question I pose is not well defined since I need to specify a machine model.
I pose the following question which may well be known - if so then please leave a comment:
Find a reasonable machine model (RAM? k-tape TM?) such that DTIME(n) on that model is NOT closed under concat. (Prob use DTIME(O(n))).
Similar for *
These are likely hard questions since if L is in DTIME(n) then L* is in NTIME(n), (similar for concat),
so I would be separating DTIME(n) from NTIME(n), which HAS been done, but not with nice naturaly problems of the type that I seek.