4 ms·
It's been a while since I studied mathematics (and I wrote my thesis in optimization), but at the time it was not clear if simplex is in P or not. I think no on
by mschulze 10y ago
It's been a while since I studied mathematics (and I wrote my thesis in optimization), but at the time it was not clear if simplex is in P or not. I think no one has found a selection function for variables that is always polynomial.
- oselhn 10y agoSee this https://en.wikipedia.org/wiki/Simplex_algorithm#Efficiency https://en.wikipedia.org/wiki/Simplex_algorithm#Efficiency. But simplex is still widely used because real problems are usually solved in polynomial time. You have to design your problem to not finish in polynomial time. But I am not a matematician this opinion it just how I understand it.