Blum and Nisan show Positive Linear Programming could be done in $NC$ if we only ask for approximate solutions. This paper https://pdfs.semanticscholar.org/8dc7/5aa9d72864022d848c3e599c5f24d9d527e7.pdf introduces monotone complexity classes in monotone Turing models.

  1. Does Positive Linear Programming have a monotone polynomial complexity?

  2. Can PLP approximation be parallelizable in $mNC$?


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.