إثبات أن مشكلة التجزئة هي مشكلة NP كاملة، مما يضاعف تحديات ضغط البيانات
2024-12-22
تُثبت ورقة بحثية نُشرت على arXiv اكتمال NP لاثنين من المتغيرات في التجزئة، المُعرّفة على أنها مشكلة ضغط مجموعة بيانات إلى ما لا يزيد عن δ رموز، إما من خلال العثور على مُفردات مباشرة (التجزئة المباشرة) أو من خلال اختيار سلسلة من عمليات الدمج (التجزئة من الأسفل إلى الأعلى). لهذه النتيجة آثار كبيرة على ضغط البيانات ومعالجة اللغات الطبيعية، مما يُبرز التحدي الهائل المتمثل في حل مشكلة التجزئة بكفاءة لمجموعات البيانات واسعة النطاق.