Typically decision problems are studied in complexity theory and function problems are studied in the Analysis of Algorithms. Unfortunately, Complexity Theory tends to abstract over the exact time complexity of a problem.
I know that Decision-Tree Complexity and more generally Query Complexity (Boolean Complexity) aim to lower bound the time complexity of decision problems. However, I'm not yet steeped in the literature and would just like to see some of the results before I spend years trying to understand them.
Even NP-Complete problems only have the trivial $\Omega(n)$ lower bounds trivial for any decision problem. I would like to find a problem with something better than this. I will also accept problems where the best algorithm we know is strongly conjectured to be optimal.
So far, I've only found the problem of recognizing palindromes.
Ultimately, I would like to attempt to prove lower bounds for some problems myself and would like to "check my answers."
