Monday, April 16, 2018

Is DTIME(n) closed under concat? star? of course not but...

(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

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 natural problems of the type that I seek.

1 comment:

  1. A historic comment about babysitting at STOC:
    This is the first *successful* babysitting at STOC.

    At the 2008 STOC in Victoria, the organizers (I remember Valerie King and Bruce Kapron) made plans for a babysitting service for the children of conference attendees. At the last minute ACM vetoed it--they were unwilling to take the risk for insurance reasons. As a resulty 3-year old son spent much time listening to Theoretical Computer Science...

    So a big Thank You to Ilias and David -- and a belated one for Valerie and Bruce!

    It is good to see progress.