# Tagged Questions

**5**

votes

**1**answer

239 views

### Feasibility of linear programs

It's known that finding the intersection of n halfplanes in 2-d takes $\Omega(n\log n)$ time. Does the lower bound apply if we change the question to deciding whether the intersection is non-empty?

**13**

votes

**4**answers

1k views

### 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 ...