چکیده
به مدت بیش از ۲۰ سال، نمونه مرجع Model-RB (frb100-40) یک چالش باز باقی مانده بود؛ از سال ۲۰۱۴، رکورد عمومی آن ۹۹ از ۱۰۰ متغیر بوده است. ما یک مجموعه مستقل ۱۰۰-رأسی قابل بررسی مستقیم برای گراف ۴٬۰۰۰-رأسی آن ارائه میدهیم. همراه با یک افراز تأییدشده به ۱۰۰ خوشهٔ ۴۰-تایی، این گواهی اثبات میکند که اندازهٔ مجموعه مستقل بیشینه ۱۰۰ و اندازهٔ پوشش رأسی کمینه ۳٬۹۰۰ است. اجرای تصادفیای که شاهد را یافت، از این فرآیند اعتبارسنجی جدا نگه داشته شده است. ما عملگرهای تعمیر جفتی و سهتایی اضافهشده را در یک کارزار از پیش ثبتشده متشکل از ۸٬۶۶۸ اجرای معتبر ارزیابی کردیم. مقایسهٔ اصلی هیچ شتابدهی قابل تشخیصی نسبت به ULSA پایه نیافت (نسبت خطر ۰٫۹۶۷، فاصله اطمینان ۹۵٪ ۰٫۹۱۵–۱٫۰۲۳؛ p=۰٫۲۴۸)، و تحلیل حذف عاملی به همین نتیجه رسید. در مجموعه FRB کوچکتر، خط لولهٔ CSP آگاه از گروه ۲٬۵۰۰ از ۲٬۵۰۰ اجرا را حل کرد، در حالی که LibMVC-NuMVC ۲٬۳۹۱ از ۲٬۵۰۰ را حل کرد. در frb100-40، ULSA کامل، ULSA پایه و NuMVC هر کدام ۰ از ۵۶ گواهی جدید تولید کردند. با نبود رویدادها، نسبتهای خطر متقاطع حلکنندههای برنامهریزیشده نامشخص باقی میمانند. NuMVC در ۴۰ اجرا با اندازهٔ پوشش ۳٬۹۰۲ و در ۱۶ اجرا با اندازهٔ پوشش ۳٬۹۰۳ به پایان رسید. شمارش جامع نشان داد که هیچیک از ۱۰۸ حالت تعارض-دوئی منحصربهفرد ثبتشده در CSP آگاه از گروه، بهبوددهندهٔ مطلقی در شعاع همینگ سه نداشت. این گواهی مسئله را حل میکند. آزمایشها مرز جستجو را مشخص میکنند و مقایسههای از پیش ثبتشده هیچ برتری ابتکاری نشان نمیدهند.
متن کامل
علوم کامپیوتر > ریاضیات گسسته
arXiv:2609.02804v1 [cs.DM] [ارسالشده در ۲ سپتامبر ۲۰۲۶]
**عنوان:** frb100-40 پس از دو دهه: گواهی بهینگی و مطالعه جستجوی پیشثبتشده
**نویسندگان:** اونور اوغورلو (دانشگاه ازمیر باکرچای)
**چکیده:** برای بیش از بیست سال، نمونه معیار Model-RB با نام frb100-40 یک چالش باز بوده است؛ از سال ۲۰۱۴، رکورد عمومی آن در مقدار ۹۹ از ۱۰۰ متغیر باقی مانده بود. ما مجموعه مستقل ۱۰۰-رأسیای ارائه میدهیم که بهطور مستقیم قابل تأیید است و متعلق به گراف ۴٬۰۰۰-رأسی آن است. همراه با افراز تأییدشده به ۱۰۰ خوشه به اندازه ۴۰، این شاهد اثبات میکند که بزرگترین اندازه مجموعه مستقل ۱۰۰ و کوچکترین اندازه پوشش رأسی ۳٬۹۰۰ است. اجرای تصادفی که این شاهد را یافت، از این اثبات مستقل نگه داشته شده است. ما عملگرهای ترمیم جفتی و سهتایی آن را در کمپین پیشثبتشدهای متشکل از ۸٬۶۶۸ اجرای معتبر ارزیابی کردیم. مقایسه پیشثبتشده هیچ بهبود قابل تشخیصی نسبت به ULSA پایه نیافت (نسبت خطر ۰.۹۶۷؛ فاصله اطمینان ۹۵٪: ۰.۹۱۵ تا ۱.۰۲۳؛ p=0.۲۴۸)، و حذف فاکتوریل نیز نتیجه مشابهی داشت. در مجموعه FRB کوچکتر، خط لوله CSP آگاه از گروه ۲٬۵۰۰ از ۲٬۵۰۰ اجرا را حل کرد، در حالی که LibMVC-NuMVC تنها ۲٬۳۹۱ مورد از آنها را حل نمود. در frb100-40، هیچیک از ULSA کامل، ULSA پایه و NuMVC نتوانستند حتی یک گواهی جدید تولید کنند (۰ از ۵۶). با وجود عدم وجود رویداد، نسبتهای خطر بینحلکنندهای برنامهریزیشده همچنان مبهم باقی ماندند. NuMVC در ۴۰ اجرا با اندازه پوشش ۳٬۹۰۲ و در ۱۶ اجرا با اندازه ۳٬۹۰۳ پایان یافت. فهرستبرداری جامع نشان داد که هیچیک از ۱۰۸ حالت تکرار تضاد منحصربهفرد ثبتشده، همسایه CSP آگاه از گروهی با بهبود قطعی در فاصله همینگ سه نداشت. این گواهی، نمونه را حل و فصل میکند. آزمایشها گلوگاههای جستجو را مشخص میسازند، و مقایسههای پیشثبتشده هیچ مزیت اکتشافیای نشان نمیدهند.
**موضوعات:** ریاضیات گسسته (cs.DM); هوش مصنوعی (cs.AI)
**استناد:** arXiv:2609.02804 [cs.DM]
https://doi.org/10.48550/arXiv.2609.02804