Skip to main content
1 of 2
Rune
  • 2.4k
  • 3
  • 23
  • 31

Super-linear time complexity lower bounds for any natural problem in NP?

Do we know any problem in NP which has a super-linear time complexity lower bound? Ideally, we would like to show that 3SAT has super-polynomial lower bounds, but I guess we're far away from that. I'd just like to know any examples of super-linear lower bounds.

I know that the time hierarchy theorem gives us problems which can be solved in O(n^3) but not in O(n^2), etc. Thus I put the word "natural" in the question.

I ask for problems in NP, because otherwise someone would give examples of EXP-complete problems.

I know there are time-space tradeoffs for some problems in NP. I don't know if any of them imply a super-linear time complexity lower bound though.

Rune
  • 2.4k
  • 3
  • 23
  • 31