Consider a linear program
$$
\max_{x} c^\top x\\
\text{s.t. } Ax \leq b\\
\text{and } x\geq 0
$$
I have been asked to comment on the "computational tractability" of such a program.
I am neither a mathematician, nor a computer scientist, but I have always heard the sentences "linear programs can be computed in polynomial time". Is this correct and what does it mean exactly? Does polynomial time relate to "computational tractability", in your view? If $x$ has dimension $10^6$, is the linear program still considered "computationally tractable"?
What is meant for an algorithm to be solved polynomial time is that the time needed for the algorithm to solve it bounded by a polynomial of the size of the input. So it means that if the size of the input gets larger and larger, the running time of the algorithm should not blow up to quickly (compared to an algorithm which runs, says, in exponential time)
A problem is said to be tractable if it is solved by a polynomial time algorithm. The definition of tractable is more a theoretic one than a practical one, because an algorithm which runs in $\mathcal{O}(n^5)$ is technically polynomial, but in practice, the size of manageable instances will still be rather low. We can also have problems for which we don't know a polynomial time algorithm, but for which we are able to solve almost all reasonably big instances with well-engineered code. In all case, tractability is about a family of instances, it is measured by how complexity scales, so we will always consider problem having a linear time algorithm to be tractable, even if no computer is able to handle an instance of size $10^{100}$.
For linear programs, we know some weakly polynomial algorithms (ellipsoid algorithm), that means that the running time of the algorithms are polynomial when we only increase the number of variables and constraints, but that we keep all the coefficients of fixed precision (64 bit floats for example). However, if we consider the family of instances where we can get not only an arbitrary big number of constraints and variables, but also an arbitrary precision on coefficients, then we don't know any polynomial algorithm to solve it (this is an open problem if we can find such an algorithm).
The simplex algorithm don't have a polynomial worst-case complexity, because we know families of instances for which complexity scales exponentially. However, we know that in average, it runs in polynomial time (and independently of the precision of the coefficients).