I read that determining the size of the maximum independent set (and also a clique of maximum size) is in P. The versions that find the actual solution are known to be NP-hard.
With respect to finding clique size, you can sort the node degrees, decrement $i$ from $|V|$ to $0$, and each time check if you have $i$ elements of node degree $i$, pick the power set of those $\geq i$ elements and verify the clique. However, picking the power set is exponential, and this algorithm would give you the solution itself. I have a hard time figuring out how you can construct an algorithm that decides the presence of a clique (or independent set) of a certain size in polytime, but doesn't give you the solution.