Séminaire Lotharingien de Combinatoire, 93B.95 (2025), 10 pp.
Tracy Chin
Real Stability and Log Concavity are coNP-Hard
Abstract.
Real-stable, Lorentzian, and log-concave polynomials are well-studied classes of polynomials, and have been powerful tools in resolving several conjectures. We show that the problems of deciding whether polynomials are real stable or log concave are coNP-hard. On the other hand, while all real-stable polynomials are Lorentzian and all Lorentzian polynomials are log concave, the problem of deciding whether a given polynomial is Lorentzian can be solved in polynomial time.
Received: November 15, 2024.
Accepted: February 15, 2025.
Final version: April 1, 2025.
The following versions are available: