Ағылшыншамен салыстырыңыз: абзацты басыңыз — түпнұсқа терезеде ашылады. Абзац астындағы EN түймесі оны мәтін ішінде көрсетеді.
Кіріспе
Есептеу күрделілігі теориясында сандық алгоритм псевдополиномиалдық уақытта жұмыс істейді, егер оның жұмыс істеу уақыты кірістің сандық мәніне (кірістегі ең үлкен бүтін санға) полиномиалды түрде тәуелді болса, бірақ міндетті түрде кірістің ұзындығына (оны көрсетуге қажетті биттер санына) емес – бұл полиномиалдық уақыт алгоритмдеріне тән. Әдетте, кірістің сандық мәні кірістің ұзындығына экспоненциалды түрде өседі, сондықтан псевдополиномиалдық уақыт алгоритмі кірістің ұзындығына қатысты полиномиалдық уақытта жұмыс істемейді. Белгілі псевдополиномиалдық уақыт алгоритмі бар NP-толық мәселе әлсіз NP-толық деп аталады. Егер P = NP болмаса, онда ол псевдополиномиалдық уақыт алгоритмімен шешілмейтіні дәлелденсе, онда NP-толық мәселе күшті NP-толық деп аталады. НП-қаттылығының күшті/әлсіз түрлері де осыған ұқсас анықталады.
In computational complexity theory, a numeric algorithm runs in pseudo polynomial time if its running time is a polynomial in the numeric value of the input (the largest integer present in the input)—but not necessarily in the length of the input (the number of bits required to represent it), which is the case for polynomial time algorithms. In general, the numeric value of the input is exponential in the input length, which is why a pseudo polynomial time algorithm does not necessarily run in polynomial time with respect to the input length. An NP complete problem with known pseudo polynomial time algorithms is called weakly NP complete. An NP complete problem is called strongly NP complete if it is proven that it cannot be solved by a pseudo polynomial time algorithm unless P = NP. The strong/weak kinds of NP hardness are defined analogously.
Бастылық сынағы
N санының жай екенін тексеру мәселесін қарастырайық, осы үшін n санына ешқандай сан толық бөлінбейтінін қарапайым тексеруге болады. Бұл тәсіл n-нің мәніне қатысты сызықтық емес, бірақ n-нің ұзындығына қатысты экспоненциалды (шамамен ). Мысалы, n санының ұзындығы 11 таңба болса да, 10 000 000 000-нан сәл кем санды тексеру үшін шамамен 100 000 бөлу операциясы қажет. Сонымен қатар, бұл алгоритмді тиімсіз ететін кіріс мәнін (мысалы, 300 таңбалы санды) оңай жазуға болады. Есептеу күрделілігі (кодталған) кіріс мәнінің ұзындығына қатысты қиындықты өлшейтіндіктен, бұл қарапайым алгоритм шынында экспоненциалды болып табылады. Дегенмен, ол псевдополиномиалдық уақытта жұмыс істейді. Бұл алгоритмді нақты полиномиалдық сандық алгоритммен салыстырайық – мысалы, екі 9 таңбалы санды қосу: екі 9 таңбалы санды қосу шамамен 9 қарапайым қадамды қажет етеді, ал жалпы алғанда алгоритм кіріс мәнінің ұзындығына қатысты шын мәнінде сызықтық болып табылады. Қосылатын нақты сандардың (миллиардтармен) мөлшерімен салыстырғанда, алгоритмді «псевдологарифмдік уақыт» деп атауға болады, бірақ мұндай термин қалыптасқан емес. Осылайша, 300 таңбалы сандарды қосу тиімсіз емес. Сол сияқты, ұзын бөлу операциясы квадраттық болып табылады: m таңбалы санды n таңбалы санға бөлу үшін қадам қажет (үлкен О белгісіне қараңыз). Жаилықты анықтау үшін, 2002 жылы ашылған, уақытта жұмыс істейтін басқа алгоритм бар екені анықталды.
Consider the problem of testing whether a number n is prime, by naively checking whether no number in divides evenly. This approach can take up to divisions, which is sub linear in the value of n but exponential in the length of n (which is about ). For example, a number n slightly less than 10,000,000,000 would require up to approximately 100,000 divisions, even though the length of n is only 11 digits. Moreover one can easily write down an input (say, a 300 digit number) for which this algorithm is impractical. Since computational complexity measures difficulty with respect to the length of the (encoded) input, this naive algorithm is actually exponential. It is, however, pseudo polynomial time. Contrast this algorithm with a true polynomial numeric algorithm—say, the straightforward algorithm for addition: Adding two 9 digit numbers takes around 9 simple steps, and in general the algorithm is truly linear in the length of the input. Compared with the actual numbers being added (in the billions), the algorithm could be called "pseudo logarithmic time", though such a term is not standard. Thus, adding 300 digit numbers is not impractical. Similarly, long division is quadratic: an m digit number can be divided by a n digit number in steps (see Big O notation.) In the case of primality, it turns out there is a different algorithm for testing whether n is prime (discovered in 2002) that runs in time .