Also known as zero-error probabilistic polynomial time
complexity class
Article · العربية
في نظرية التعقيد الحسابي القسم ZPP هو قسم كل المسائل التي يمكن تقريرها بواسطة آلة تيورنج احتمالية بوقت حدودي مع إمكانية الفشل في الاتيان بجواب، أيضا تعريف هذا القسم بأنه قسم كل المسائل التي يمكن تقريرها بواسطة آلة تيورنج احتمالية التي لا تخطئ أبدًا بحيث أن وقتها المتوقع (expected running time) هو حدودي أي أي لو أن الخوارزمية ترمي قطع نقدية عشوائية خلال وقت عملها فإنَّ جوابها صحيح دائما ولكن معدل وقت عملها لكل مُدخل طوله هو (p(n ، حيث أنَّ (p(n هو كثير حدود، القول الاخير يعني انه بشكل عام وقت عمل الخوارزمية هو كثير حدود ولكن يمكن أن يكون هناك مُدخلات بحيث أن وقت عمل الخوارزمية أكثر من حدودي. التعريفان متكافئان.
Abstract from DBpedia / Wikipedia · CC BY-SA