محمدحسین با تعدادی از دوستانش به تماشای یک مسابقه‌ی اسب‌دوانی رفته است. او با هر یک از دوستانش یک شرط به این صورت بسته است که مثلاً دوستِ شماره‌ی ‎$i$‎ام ادعا کرده که یکی از اسب‌های مجموعه‌ی ‎$A_i$‎ مقام ‎$r_i$‎ را به دست می‌آورد. قبل از بستن این شرط نیز دوست ‎$i$‎ام ‎$x_i$($0 < x_i < 1$)‎ تومان به عنوان هزینه‌ی شرط‌بندی به محمدحسین داده است. در صورتی که ادعای این دوست درست از آب در بیاید محمدحسین باید یک تومان به او بدهد. آیا الگوریتمی با زمان چندجمله‌ای وجود دارد که با گرفتن این اطلاعات ‎($x_i$ها،‎ ‎$r_i$ها و مجموعه‌های ‎$A_i$‎) ببیند که آیا ممکن است نتیجه‌ی مسابقه طوری شود که محمدحسین در کل ضرر کند.

• سوال بعد
• سوال قبل