Can this statement be confirmed or disproved:
$\mathsf{DTime}(O(n^k)) \subseteq \mathsf{NTime}(g)$ for some $g \in o(n^k)$
[Question changed to use Kaveh's brilliant formulation.]
Here the NDTM must "outrun" the DTM.
This seems similar to the PvNP question, but I'm not sure...
Thanks!
EDIT: This question seeks an inequality between the run time of polytime DTM deciders and their corresponding NP verifiers. If k=1, the proposition fails (e.g.: determining parity requires n steps on a TM and therefore a verifier cannot take any shortcuts). But if k>=2 ...?
I wonder if the statement can be disproved without leading to any major or unexpected complexity class separations... Is there a diagonalization argument that could work here.