В английском языке есть слово "complexity" - судя по известной мне периодике, в математических статьях этот термин кратко описывает особый род сложности математических задач, который может быть выражен в терминах вычислимости - очень грубо говоря, complexity - такой род сложности, при котором при сохранении фундаментальной сущности задачи происходит нелинейный рост объема вычислений при, например, увеличении размерности или при замене одних элементов другими, более сложными (рациональные числа заменить на вещественные, и т.д.).

Ну, то есть если говорят о сложности - то имеют в виду именно NP-complexity, поскольку с P-complexity иметь дело несложно (ха-ха).

Нужен точно такой же термин в русском языке, чтобы он был емкий и понятный, и чтобы сразу было понятно, что под сложностью имеется в виду не просто сложность, а именно вычислительная сложность, и именно такая, какая описана выше. Просто сложность, как это обычно переводят, не подходит сюда совсем.

Что можно предложить, как вы считаете?

Мне кажется, если подобный термин появится и будет внедрен, мало того, что переводить статьи без потери смысла или избыточности сразу станет проще (это самая меньшая из проблем) - подобное нововведение позволит отразить в русском языке некоторые современные фундаментальные проблемы праксеологии.

В английском языке они отражены на уровне того, что, когда открываешь статью о computability, встречая этот термин, сразу понимаешь, что имеется в виду.