Не существует простого способа это сделать, но есть ряд признаков:

• ваш алгоритм быстро работает при малом количестве элементов, но сильно замедляется при увеличении их числа;
• формулировка часто указывает на NР-полноту задачи;
• вам приходится вычислять все возможные варианты Х, потому что задачу невозможно разбить на меньшие подзадачи? Такая задача может оказаться NР-полной;
• если в задаче встречается некоторая последовательность (например, последовательность городов, как в задаче о коммивояжере) и задача не имеет простого решения, она может оказаться NР-полной;
• если в задаче встречается некоторое множество (например, множество радиостанций) и задача не имеет простого решения, она может оказаться NР-полной;
• можно ли переформулировать задачу в условиях задачи покрытия множества или задачи о коммивояжере? В таком случае ваша задача определенно является NР-полной.

У NP-полных задач не бывает известных быстрых решений. Если у вас имеется NP-полная задача - лучше воспользоваться приближенным алгоритмом.

Oct. 12, 2023, Источник