I was just wondering what the complexity of the PageRank problem is. A description can be found here: http://en.wikipedia.org/wiki/PageRank . (I am referring to the problem that is solved by the PageRank algorithm, i.e., the question of how one should reasonably distribute "ranking" throughout a graph in a way that is consistent with the model presented in the article I've linked to.)
I've always been curious as to whether or not there is a deterministic polynomial time algorithm that can do as well as the actual PageRank algorithm that Google uses.
It's clear to me that the problem is FNP at worst, as it's easy to verify if a given "arrangement" of rankings for a series of nodes is consistent and valid. I'm not sure beyond that, though. Is it NP-hard? I cannot think of which NP-complete problem would reduce to it.