مبرهنة شوارتز-زيبل

من ويكيبيديا، الموسوعة الحرة
(بالتحويل من مبرهنة شوارتز -زيبل)
اذهب إلى: تصفح، ‏ ابحث

مبرهنة شوارتز -زيبل هي نتيجة اساسية في علم الاحتمال ولها تأثير على عدة مجالات في الرياضيات وعلم الحاسوب

مقدمة[عدل]

من الشائع جدا معرفة متطابقات متعددة الحدود مثل : x^2-y^2=(x-y)(x+y) او مبرهنة المربعات الأربع للاغرانج وهي : (a_1^1+a_2^2+a_3^3+a_4^4)(b_1^1+b_2^2+b_3^3+b_4^4)=(a_1 b_1-a_2 b_2-a_3 b_3-a_4 b_4)^2+(a_1 b_2+a_2 b_1 +a_3 b_4 -a_4 b_3)^2+(a_1 b_3 -a_2 b_4 +a_3 b_1 +a_4 b_2)^2+(a_1 b_4 + a_2 b_3 -a_3 b_2 + a_4 b_1)^2 وهناك طريقة بسيطة لفحص هذه المتطابقات وهي عن طريق فتح الأقواس وفحص كل منهما اذا ما كانا متطابقين ! ولكن هذه العملية هي عملية أُسية بالنسبة لطول المدخل , اذ ان عدد احادية الحدود الناتجة عدد هو \binom{n+d}{d} عندما d هو اعلى درجة احادي الحدود وما نريده اذا هي خوارزمية سريعة (اي تعقيدها الوقتي هو متعدد حدود بالنسبة للمدخل ) ولكن هذا غير معلوم للان ومبرهنة شوارتز-زيبل تعطينا خوارزمية احتمالية سريعة .

تعريف المسألة[عدل]

مسألة تطابق متعددات الحدود هي : معطى دائرة حسابية  C والتي تحسب متعدد الحدود p(x_1,...,x_n) في F[x_1,x_2, ... ,x_n] , جد خوارزمية حتمية التي تفحص اذا ما p صفر ويستخدم فقط Poly(size(C)) حسابات في \mathbb{F}

المبرهنة[عدل]

لنفرض ان  P \in F[x_1,x_2,...,x_n] متعدد حدودي ليس صفرا ودرجته  d \ge 0 فوق حقل \mathbb{F} ولنفرض ان S مجموعة جزئية نهائية ل-\mathbb{F} حينها :

 Pr_{r_1,r_2,...,r_n\in S}[P(r_1,r_2,...,r_n)=0]\le \frac{d}{|S|}

البرهان[عدل]

سوف نستخدم استقراء رياضي (Induction) على n ,

اذا n=1 , حسب المبرهنة الأساسية في الجبر هناك على الاكثر d جذور لذا فان المبرهنة تصح في هذه الحالة اي انه :  Pr_{r_1\in S}[P(r_1)=0]\le \frac{d}{|S|}

لنفرض ان المبرهنة صحيحة لكل متعددات الحدود مع  n-1 متغيرات وبدون تقييد العموم نستطيع ان نفترض ان  p متعدد الحدود ب- x_1 ونستطيع ان نكتبه بالطريقة التالية :

p(x_1,x_2,...,x_n)=\sum_{i=1}^d x_1^i p_i(x_2,...,x_n)

بما ان p ليس صفرا يوجد i بحيث ان  p_i ليس صفراً ونختار i ليكون الأكبر وصفته كما هو مذكور , مفهوم ضمنا أن  deg(p_i) \le d-i وذلك لان متعدد احادي الحدود  x_1^i درجته i وبما ان حاصل ضرب متعدد الحدود : p_i(x_2,...,x_n) مع احادي الحدود هذا هو على الاكثر d لذا فان هذه الصفة صحيحة . الان نختار عشوائيا r_2,r_3,...,r_n من S , وحسب فرضية الاستقراء الرياضي :

Pr_{r_2,...,r_n\in S}[p_i(r_1,r_2,...,r_n)=0]\le \frac{d-i}{|S|}

.

اذا p_i(r_2,...,r_n)\neq 0 حينها  p(x_1,r_2,...,r_n) والذي يحوي متغير واحد فقط ما يعيدنا للحالة الاساسية للاستقراء الرياضي اي :

 Pr[p_i(r_1,...r_n)=0|p_i(r_2,...,r_n)\neq 0] \le \frac{i}{|S|}

حينها :

 Pr[p(r_1,...r_n)=0]\le Pr[p_i(r_2,...r_n)=0]+Pr[p_i(r_1,...r_n)=0|p_i(r_2,...,r_n)\neq 0] \le \frac{d-i}{|S|}+\frac{i}{|S|} = \frac{d}{|S|}

استخدامات[عدل]

  1. هذه المبرهنة تقول بانه اذا كان عندنا في الحقل \mathbb{F} على الاقل 2d اعداد عندها يوجد خوارزمية احتمالية واحتمال خطأه على الاكثر \frac{1}{2} وفي حالة انه يوجد اقل حينها نوسع \mathbb{F} ونختار نقاط عشوائية لذا فان هذه المسألة تتبع قسم التعقيد co-RP .
  2. المبرهنة والتي تبحث مسألة تطابق متعددي حدود لها الكثير من التطبيقات في علم الحاسوب والرياضيات حيث ان مسألة التطابق كانت مهمة في برهنة  IP=PSPACE مسألة اخرى هي فحص اذا ما مخطوط معطى هو مخطط ثنائي وذلك حسب نظرية برهنها Tutte . ويمتد استخدامها لفحص اذا ما معطى عدد هو اولي .