I have been stuck on this for a while now:Claim: Suppose we can decide an NP-complete problem with an algorithm in $T(n) \geq n^2$ time. Then,we can write down an algorithm that prints a solution in $O(T(n)^2)$ time. Prove that this statement is true when the NP-complete problem to be decided is 3-SAT, Clique, or Hamiltonian-Path. Can someone help me with at least one of these?
Solving problems in NP-complete
complexity theory