np


np – /N-P/, преф. В высшей степени, чрезвычайно. Используется в качестве усилительной приставки в прилагательных, описывающих степень сложности, в значении «еще более трудный, чем кажется». (Все NP-полные задачи, по-видимому, очень трудные, однако до сих пор никто не смог найти априорную причину, признак, по которым можно было бы определить, что задача должна быть именно таковой.) «Заставить этот алгоритм работать корректно для каждого конкретного случая будет NP-несносной задачей.» Приставка NP-взята как составная часть терминов «NP-полный», «NP-сложный» из теории алгоритмов. «NP-» означает множество недетерминированных полиномиальных алгоритмов, т.е. тех, которые могут быть завершены недетерминированной машиной Тьюринга за промежуток времени, являющийся полиномиальной функцией размера задачи. Решение одной «NP-полной» задачи позволило бы решить все остальные задачи.