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 youPs.: 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
Implications of the class of problems with parallel solutions being not P-complete for optimization of matrices
complexity theory;optimization;parallel computing;linear programming