Inf прав, когда намекнул на сложность и приводимость, а не только на то, что вовлечено / включено в реализацию алгоритма. Это предположения, которые вы делаете.
Все части кода написаны с предположениями о мире, в котором он работает. Эти предположения являются более фундаментальными, чем код, написанный с этими предположениями. Короче говоря, я бы сказал: если что-то использует или оспаривает предположение, тогда оно менее фундаментально, чем это предположение .
Давайте рассмотрим пример: сортировка. Проблема сортировки заключается в том, что когда все делается наивно, время, необходимое для сортировки, очень быстро растет. С технической точки зрения проблема сортировки имеет тенденцию к тому, чтобы быть NP завершенной. Таким образом, алгоритмы сортировки разрабатываются с целью избежать завершения NP. Но всегда ли NP завершен медленно? Это проблема сама по себе, и проблема называется P! = NP, которая до сих пор не была доказана ни как истинная, ни как ложная. Так что P! = NP является более фундаментальным, чем сортировка.
Но даже P! = NP делает некоторые предположения. Предполагается, что проблемы с завершением NP всегда могут быть выполнены до конца, даже если для их завершения требуется много времени. Другими словами, запись big-O для полной задачи NP никогда не бывает бесконечной. Возникает вопрос: все ли проблемы гарантированно имеют точку завершения? Ответ на этот вопрос - нет, не все задачи имеют гарантированную точку завершения, самой тривиальной из которых является бесконечный цикл: while (1) {print "still running!"}. Так можем ли мы обнаружить все случаи программ, запущенных бесконечно? Нет, и доказательством этого является проблема остановки. Следовательно, проблема остановки является более фундаментальной, чем P! = NP.
Но даже проблема остановки делает предположения. Мы предполагаем, что все наши программы выполняются на конкретном типе процессора. Можем ли мы рассматривать все процессоры как эквивалентные? Есть ли процессор, который можно построить, чтобы решить проблему остановки? Что ж, ответ таков, пока ЦП завершен по Тьюрингу, они эквивалентны другим ЦП, завершившим Тьюринг. Поэтому полнота по Тьюрингу является более фундаментальной проблемой, чем проблема остановки.
Мы можем продолжать и подвергать сомнению наши предположения, такие как: все ли виды сигналов эквивалентны? Возможно ли, что жидкостный или механический компьютер будет принципиально отличаться от электронного компьютера? И это приведет нас к таким вещам, как теория информации Шеннона, булева алгебра и т. Д., И каждое допущенное нами предположение более фундаментально, чем приведенное выше.