Let M be a deterministic Turing Machine that runs in time On

Let M be a deterministic Turing Machine that runs in time O(n²) and accepts the set S.

Which of the following are true and which are false.

1. The set S is always in DSPACE(n²)?

2. The set S can be in DTIME(n)?

3. The set S is always in NTIME(n²)?

4. The set S must be non-empty?

Solution

The set S is always in DSPACE(n2) True

The set S can be in DTIME(n) False

The set S is always in NTIME(n2) True

The set S must be non-empty True