МА́ССОВАЯ ПРОБЛЕ́МА

МА́ССОВАЯ ПРОБЛЕ́МА, про­бле­ма на­хо­ж­де­ния ал­го­рит­ма для ре­ше­ния бес­ко­неч­ной се­рии од­но­тип­ных за­дач, за­ви­ся­щих от не­ко­то­ро­го па­ра­мет­ра. Про­стей­шие при­ме­ры М. п.: сло­жить 2 дан­ных чис­ла, ум­но­жить 2 дан­ных чис­ла, про­ве­рить, яв­ля­ет­ся дан­ное це­лое чис­ло про­стым или нет, раз­ло­жить дан­ную функ­цию в сте­пен­ной ряд. Ес­ли та­ко­го ал­го­рит­ма не су­ще­ст­ву­ет, то го­во­рят, что рас­смат­ри­вае­мая М. п. не­раз­ре­ши­ма. За­да­чу о су­ще­ст­во­ва­нии ал­го­рит­ма, ре­шаю­ще­го дан­ную М. п., ино­гда на­зы­ва­ют про­бле­мой раз­ре­ши­мо­сти. Этот тер­мин впер­вые поя­вил­ся в свя­зи с про­бле­мой рас­по­зна­ва­ния вы­во­ди­мо­сти фор­мул в клас­сич. ис­чис­ле­нии пре­ди­ка­тов. Во­об­ще го­во­ря, про­бле­мой раз­ре­ши­мо­сти дан­ной М. п. ес­те­ст­вен­но счи­тать за­да­чу о том, раз­ре­ши­ма или нет эта М. п., т. е. во­прос о су­ще­ст­во­ва­нии ис­ко­мо­го ал­го­рит­ма.

См. так­же Ал­го­рит­ми­че­ская про­бле­ма.