NP толықтығы әлсіз - Weak NP-completeness

Жылы есептеу күрделілігі, an NP аяқталды (немесе NP-hard ) мәселе болып табылады әлсіз NP-аяқталған (немесе әлсіз NP-hard), егер бар болса алгоритм жұмыс уақыты болатын мәселе үшін көпмүшелік проблеманың өлшемінде және қатысатын деректердің шамаларында (егер олар берілген болса) бүтін сандар ), негіз-екеуінен гөрі логарифмдер олардың шамаларының Мұндай алгоритмдер техникалық жағынан экспоненциалды олардың кіріс өлшемдерінің функциялары және сондықтан қарастырылмайды көпмүшелік.

Мысалы, NP-hard рюкзак мәселесі шешуге болады динамикалық бағдарламалау рюкзактың өлшемі мен элементтердің санында полиномдық бірнеше қадамдарды қажет ететін алгоритм (барлық деректер масштабталған деп санағанда, бүтін сандар); дегенмен, бұл алгоритмнің жұмыс уақыты экспоненциалды уақыт заттар мен рюкзактардың кіріс өлшемдері олардың шамаларында логарифмдік болғандықтан. Алайда, Гарей мен Джонсон (1979) байқағандай, «А жалған полиномдық уақыт алгоритм… бізді қызықтыратын қолданба үшін сирек кездесетін [экспоненциальды үлкен] сандармен кездескенде ғана «экспоненциалды мінез-құлықты» көрсетеді. Олай болса, алгоритмнің бұл түрі біздің мақсатымызға да, сонымен қатар уақыттың көпмүшелік алгоритмі ». Толығырақ проблема үшін тағы бір мысал - бұл қосынды қосындысының мәселесі.

Байланысты термин толық NP (немесе бірыңғай NP-толық) деректер кодталған болса да, NP-де толық қалады деген мәселелерді білдіреді унарий (яғни егер деректер жалпы кіріс өлшеміне қатысты «кішкентай» болса).

Әдебиеттер тізімі

  • М.Р.Гери және Д.С.Джонсон. Компьютерлер және қиындықтар: NP-толықтығы теориясының нұсқауы. В.Х. Фриман, Нью-Йорк, 1979 ж.
  • Л. Холл. Есептеудің күрделілігі. Джонс Хопкинс университеті.