Skip to main content
added 259 characters in body
Source Link
Gil Kalai
  • 24.7k
  • 38
  • 235
  • 327

The shortFor the circuit model, the answer is NO. The best general lower bounds are linear.

(As Ryan explained in his answer and comment for multi tape Turing machines there are (slightly) superlinear bounds. As far as I understand from his comment for random access Turing machines there are no superlinear lower bounds known.)

The short answer is NO. The best general lower bounds are linear.

For the circuit model, the answer is NO. The best general lower bounds are linear.

(As Ryan explained in his answer and comment for multi tape Turing machines there are (slightly) superlinear bounds. As far as I understand from his comment for random access Turing machines there are no superlinear lower bounds known.)

Source Link
Gil Kalai
  • 24.7k
  • 38
  • 235
  • 327

The short answer is NO. The best general lower bounds are linear.