I am not a specialist on computational complexity theory. I do work on optimization and I am currently researching about the implications of the class of problems with parallel solutions (NC) being not P-complete, i.e., NC$\neq$P for optimization. In particular, I am interested about the consequences for equations based on matrix optimization problems.

For instance, given a square matrix $A$ find a positive definite matrix $M$ with same dimensions and such that $AM+MA^\top$ is negative definite.

Could someone elaborate on the difficulties to make a parallel algorithm, assuming that NC$\neq$P, to verify the negativeness of $AM+MA^\top$? Also, could someone provide a reference (article or book) that contain a similar explanation?

Thank you

Ps.: I also started to read the book [1] but, since I am not a specialist on complexity theory, I cannot grasp the details regarding the limitations explained by the authors. I understood that there are evidences suggesting that NC$\neq$P.

[1] Raymond Greenlaw, H. James Hoover, Walter L. Ruzzo "Limits to Parallel Computation: P-Completeness Theory", Oxford University Press

  • $\begingroup$ Be aware that NC covers a quite artificial notion of parallel computing. Depending on which questions you are interested in, it may not at all be helpful for you. $\endgroup$ – Raphael Sep 15 '16 at 10:59

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.