Real Stability and Log Concavity are coNP-Hard

2024/04/30 by Tracy Chin, Chin, Tracy
Engineering · #Combinatorics (math.CO) #Computational Complexity (cs.CC) #Control and Stability of Dynamical Systems #FOS: Computer and information sciences #FOS: Mathematics #Optimization and Control (math.OC)

paper · pdf · doi:10.48550/arxiv.2405.00162

openalex publication_date 2024/04/30 · openalex created_date 2024/05/03 · openalex updated_date 2026/07/28

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 a polynomial of fixed degree is real stable or log concave are coNP-hard. On the other hand, while all homogeneous real-stable polynomials are Lorentzian and all Lorentzian polynomials are log concave on the positive orthant, the problem of deciding whether a polynomial of fixed degree is Lorentzian can be solved in polynomial time.

Related

• \K-Lorentzian and \K-CLC Polynomials in Stability Analysis
• Preservation of log-concavity on gamma polynomials
• K-Lorentzian Polynomials
• Lorentzian polynomials
• Volume Polynomials and Log-concavity of the Characteristic Polynomials of Matroids