“Assuming correctness, it seems extremely likely, if not already a direct consequence…”
Bernardo Subercaseaux 🐒 @b_subercaseauxX
Archived text
@rrwilliams Assuming correctness, it seems extremely likely, if not already a direct consequence, that NTIME[t] subseteq DTIME[2^{o(t)}]. It comes down to reducing the auxiliary variables in the CNF encoding of NTIME-acceptance!