#optimization

Given a real $m\times n$ matrix $A$ and a vector $b\in {\mathbb{R}}^m$, decide whether there is $x\in {\mathbb{R}}^n$ with $Ax\ge b$. Is there an algorithm whose number of arithmetic operations is bounded by a polynomial in $m$ and $n$ alone, independent of the size of the numbers in $A$ and $b$?

Prove that no packing of equal balls in three-dimensional space has average density greater than $\pi /\sqrt{18}\approx 0.7405$, the density of the familiar cannonball stacking (face-centered cubic packing).

A rigid planar shape must be moved around a right-angled corner in a hallway of width 1. What is the largest possible area of such a shape? Gerver's sofa has area about 2.2195. Prove that no shape with larger area can make the turn.