Recently I’ve been studying for an exam, however, I’ve been really struggling to understand some NP-related exercises.

Specifically, I’ve been stumped by these two tasks in particular:

a)

Examine whether 3-SAT ∈ NTIME(n^2). Justify your answer.

b)

There exists a language L2 ∈ NTIME(n^3) such that L2 ̸∈ NTIME(n^2). Prove or disprove:
L2 ≤p,m 3-SAT

I’ve been trying to solve it, but I’m unsure of if I’m solving them properly or not. Here’s what I am currently at in my thought process:

For a):
We know that 3-SAT is NP-complete via Cook’s Theorem. Therefore, it’s part of NP, like NTIME(n^2) is.
However, that alone doesn’t allow us to say for sure that it’s part of NTIME(n^2) or not. All we know is that it takes polynomial time for an NTM to decide it.
Theoretically we can have the NTM guess a value for each of the n literals (which would be O(n) time), but then we also need to check if all the k clauses include a 1 or not, which would take O(k) time.

The issue I’m facing is basically, I don’t know how to proceed from this point on in concretely proving if it’s in NTIME(n^2) or not, especially since k, i.e. the number of clauses, can both be higher and lower than n, i.e. the number of different literals.

For b):
Because we have L2 ∈ NTIME(n^3), and NTIME(n^3) ∈ NP, that means that L2 ∈ NP. Because 3-SAT is NP-complete via Cook’s theorem, it is therefore NP-hard. And because it is NP-hard, it holds that for all L ∈ NP that: L ≤p,m 3-SAT.
And since L2 ∈ NP, it follows that L2 ≤p,m 3-SAT.

The issue here for me is basically: It sounds solid, but it seems too easy for an answer. Most worrying is the fact that I didn’t use the fact that L2 ̸∈ NTIME(n^2) here, because I simply didn’t know how I should bring it in.

So now I turn to you. Was I on the right path or was I completely off the mark? And how should I continue with the proof for a)? If I was completely wrong in these attempts, I would greatly appreciate any solutions and/or correct ways to approach this. Any tips for other tasks of this nature would also be quite helpful.