I think the length of this code speaks for the complexity of this problem. Or rather, its lack there of.
problem = []
for a in range(2, 101):
for b in range(2, 101):
if a**b not in problem:
problem.append(a**b)
print len(problem)