هذه المقالة يتيمة إذ تصل إليها مقالات أخرى قليلة جدًا. فضلًا، ساعد بإضافة وصلة إليها في مقالات متعلقة بها. (نوفمبر 2017)

يفتقر محتوى هذه المقالة إلى الاستشهاد بمصادر. فضلاً، ساهم في تطوير هذه المقالة من خلال إضافة مصادر موثوق بها. أي معلومات غير موثقة يمكن التشكيك بها وإزالتها. (مارس 2016)

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

من الشائع جدا معرفة متطابقات متعددة الحدود مثل: ${\displaystyle x^{2}-y^{2}=(x-y)(x+y)}$ أو مبرهنة المربعات الأربع للاغرانج وهي:

${\displaystyle (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}}$

وهناك طريقة بسيطة لفحص هذه المتطابقات وهي عن طريق فتح الأقواس وفحص كل منهما إذا ما كانا متطابقين ! ولكن هذه العملية هي عملية أُسية بالنسبة لطول المدخل، إذ ان عدد احادية الحدود الناتجة عدد هو ${\displaystyle {\binom {n+d}{d}}}$ عندما d هو اعلى درجة احادي الحدود وما نريده إذا هي خوارزمية سريعة (أي تعقيدها الوقتي هو متعدد حدود بالنسبة للمدخل) ولكن هذا غير معلوم للان ومبرهنة شوارتز-زيبل تعطينا خوارزمية احتمالية سريعة.

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

لنفرض ان ${\displaystyle P\in F[x_{1},x_{2},...,x_{n}]}$ متعدد حدودي ليس صفرا ودرجته ${\displaystyle d\geq 0}$ فوق حقل ${\displaystyle \mathbb {F} }$ ولنفرض ان S مجموعة جزئية نهائية ل-${\displaystyle \mathbb {F} }$ حينها:

${\displaystyle Pr_{r_{1},r_{2},...,r_{n}\in S}[P(r_{1},r_{2},...,r_{n})=0]\leq {\frac {d}{|S|}}}$

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

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

لنفرض ان المبرهنة صحيحة لكل متعددات الحدود مع ${\displaystyle n-1}$ متغيرات وبدون تقييد العموم نستطيع ان نفترض ان ${\displaystyle p}$ متعدد الحدود ب-${\displaystyle x_{1}}$ ونستطيع ان نكتبه بالطريقة التالية:

${\displaystyle p(x_{1},x_{2},...,x_{n})=\sum _{i=1}^{d}x_{1}^{i}p_{i}(x_{2},...,x_{n})}$

بما ان ${\displaystyle p}$ ليس صفرا يوجد i بحيث ان ${\displaystyle p_{i}}$ ليس صفراً ونختار i ليكون الأكبر وصفته كما هو مذكور، مفهوم ضمنا أن ${\displaystyle deg(p_{i})\leq d-i}$ وذلك لان متعدد احادي الحدود ${\displaystyle x_{1}^{i}}$ درجته i وبما ان حاصل ضرب متعدد الحدود:${\displaystyle p_{i}(x_{2},...,x_{n})}$ مع احادي الحدود هذا هو على الأكثر d لذا فان هذه الصفة صحيحة. الآن نختار عشوائيا ${\displaystyle r_{2},r_{3},...,r_{n}}$ من ${\displaystyle S}$ , وحسب فرضية الاستقراء الرياضي:

${\displaystyle Pr_{r_{2},...,r_{n}\in S}[p_{i}(r_{1},r_{2},...,r_{n})=0]\leq {\frac {d-i}{|S|}}}$

.

إذا ${\displaystyle p_{i}(r_{2},...,r_{n})\neq 0}$ حينها ${\displaystyle p(x_{1},r_{2},...,r_{n})}$ والذي يحوي متغير واحد فقط ما يعيدنا للحالة الاساسية للاستقراء الرياضي أي:

${\displaystyle Pr[p_{i}(r_{1},...r_{n})=0|p_{i}(r_{2},...,r_{n})\neq 0]\leq {\frac {i}{|S|}}}$

حينها:

${\displaystyle Pr[p(r_{1},...r_{n})=0]\leq Pr[p_{i}(r_{2},...r_{n})=0]+Pr[p_{i}(r_{1},...r_{n})=0|p_{i}(r_{2},...,r_{n})\neq 0]\leq {\frac {d-i}{|S|}}+{\frac {i}{|S|}}={\frac {d}{|S|}}}$

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