> the state of the art lower bounds on time complexity of algorithms for solving 3SAT is O(n)

Wow, that’s pretty stark.

“What’s the minimum time it would take to solve this problem?”

“Well, at the very least you’d have to read the input the whole way through”