تابعی به زبان پاسکال عجیب بنویسید که مسئله وجود جواب برای $SAT$ را در زمان چند جمله‌ای حل کند. متغیرهای از نوع $integer$ در زبان پاسکال عجیب نامحدود است (هر عدد صحیح را می‌توان در آن‌ها ذخیره کرد) و هر محاسبه در زمان ثابت انجام می‌شود.

در نوشتن تابع خود فرض کنید تعداد متغیرها در $n$ و تعداد عبارات در $m$ داده شده است. همچنین عبارات $SAT$ در آرایه $L$ با ابعاد $m*n$ داده شده است که $L[a,b]$ برابر است با:

• ۰ اگر متغیر $b$ ام در عبارت $a$ ام نباشد.
• ۱ اگر متغیر $b$ ام در عبارت $a$ ام باشد.
• ۱- اگر نقیض متغیر $b$ ام در عبارت $a$ ام باشد.

اگر بتوان به متغیرها به شکلی مقادیر True و False نسبت داد به‌طوری که حداقل یکی از جمله‌های هر عبارت True باشد تابع باید مقدار True و در غیر این صورت False برگرداند. (منظور از هر جمله یک متغیر یا نقیض آن است که در عبارت آمده است)

راهنمایی: می‌توانید از دستورات $for،if،shr،shl،not،xor،or،and$ و عملگرهای محاسباتی و آرایه‌ها استفاده کنید که همگی زمان اجرای ثابت دارند.

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