Besides the classical: you can't do comparison sort with fater faster than (n logn); what are other lower bounds we know of for algorithms? I can't seem to dig them up via google scholar, yet they must exist.

I'm especially interested in polynomial time algorithms (i.e. and not proofs of: you can't solve this in polynomial time unless P = NP).

Thanks!

Note: marked as community wiki now

Besides the classical: you can't do comparison sort with fater than (n logn); what are other lower bounds we know of for algorithms? I can't seem to dig them up via google scholar, yet they must exist.

I'm especially interested in polynomial time algorithms (i.e. and not proofs of: you can't solve this in polynomial time unless P = NP).

Thanks!

Note: marked as community wiki now

Besides the classical: you can't do comparison sort with fater than (n logn); what are other lower bounds we know of for algorithms? I can't seem to dig them up via google scholar, yet they must exist.

I'm especially interested in polynomial time algorithms (i.e. and not proofs of: you can't solve this in polynomial time unless P = NP).

Thanks!