استكشف روعة أر بي (تعقيد حسابي)

في علم التعقيد الحسابي RP أو Randomized Polynomial time هو قسم المسائل التي تقريرها بوقت حدودي بواسطة آلة تيورنج احتمالية مع الخاصية التالية:



إذا كان المُدخل جوابه نعم حينها احتمال أن الجواب هو نعم أكبر من











1

2









{\displaystyle {\frac {1}{2}}}





إذا كان المُدخل جوابه لا حينها احتمال ان الجواب هو لا هو 1 .

أي انه إذا كان الجواب نعم فهو حتما نعم اما إذا كان الجواب لا فانه باحتمال 1/2 على الأقل ان يكون الجواب لا .

يمكن استبدال الثابت 1/2 بأي عدد لا يساوي 0 اقل من 1 .