However, isn’t there another distinction between the problems? In the case of LP with integral (or rational) inputs, isn’t it the case that the polytime algorithms can be modified to produce an exact rational expression for the optimum? In the case of SDP with the same inputs all we have is an approximation scheme with a running time that is polynomial in log (1/epsilon). Now if one wants a binary/decimal expression of the optimum then the two produce the same quality of answer but I don’t know of an efficient SDP algorithm that produces a closed form expression. (Obviously it is not rational in the SDP case but any closed-form expression, say radicals, would do.)

]]>Just an idea.

]]>* The link with complexity theory has to do with social complexity * ** snip **

Are you practicing to do a Feynman? or maybe the other way — publish a social paper in a scientific journal. It certainly seems that you are practicing in their gobbling writing style. Being neither here nor there, being untrue to both fields.

]]>Needless to say, from a purely algorithmic point of view, this should never happen. So why does it happen?

The link with complexity theory has to do with *social complexity* … Wolfram Research has known and acknowledged their SVD problem for almost a year, but are disinclined to fix it (it being unprofitable to do so).

This raises the practical question: as a citizen of a Jeffersonian democracy, should I meekly submit to market forces, or should I seek to obtain the four freedoms of Free-as-in-Freedom software, and therefore, abandon Mathematica for less-convenient free software packages?

Up until recently, I would have considered this as a dilemma in economics and/or moral philosophy. And pragmatically, I am in the “meekly submitting” category … although I grit my teeth daily at the ugliness of the resulting code circumlocutions!

But nowadays, and increasingly, it seems that “sociocomplexity” (which is broadly analogous to sociobiology) is emerging the most creative intellectual venue for analyzing these problems.

The economist Amartya Sen is a leader in considering these issues. A recent essay of Sen’s ends with these words:

*As Buddha said, “there are some questions that can be asked of which there are no answer” and while I’ve given several answers, they are not final answers, and I very much hope to have more discussion on these topics.*

Am I the only one who sees, narrowly in dealing with bugs in **SingularValueDecomposition[]**, broadly in Sen’s article, an emerging challenge in complexity theory?

Practically, we can solve LPs much, much faster than SDPs, and we can do matrix inversion and SVD faster than solving a generic LP. We are talking two orders of magnitude in the size of a program that can be feasibly solved (LP vs. SDP).

But for your aesthetic, it’s probably best not to allow arbitrary P-time or log-space reductions; if you restrict your effort to syntactic translations, then you will get an actual hierarchy.

]]>