حدود أدنى من مجموع المربعات الموزونة للحدود أدنى للمتعددات الحدود الأحادية تقتضي VP VNP

الملخص بالنسبة لمتعدد الحدود f، فإن تمثيل مجموع المربعات الموزونة (SOS) له الشكل f = ₈ ₒ cᵢ fᵢ² f = ∑ i ∈ s c i f i 2، حيث أن الأوزان cᵢ c i هي عناصر المجال. حجم التمثيل هو عدد الحدود الفردية التي تظهر عبر fᵢ f i. الحد الأدنى له عبر جميع التحليلات من هذا النوع يسمى دعم-المجموع S (f) لـ f. لمتعدد حدود أحادي f من الدرجة d من دعم كامل، تكون حد أدنى لدعم-المجموع هو S (f) d S (f) ≥ d. نحن نثبت أن وجود متعدد حدود أحادي صريح f مع دعم-مجموع أكبر قليلاً من الحد الأدنى، أي S (f) d^0. 5+ S (f) ≥ d 0. 5 + ε، لبعض > 0 ε > 0، يقتضي أن ≠، وهي المشكلة الرئيسية المفتوحة في التعقيد الجبري. في الواقع، تعمل براهيننا بالنسبة لبعض الدوال دون الثابت (d) > 0 ε (d) > 0 أيضاً. ندرس أيضًا تمثيل مجموع المكعبات (SOC) للمتعددات الحدود. نثبت أن متعدد حدود صريح صعب يستوجب أن يكون كل من blackbox-PIT في، و ≠.