В какой степени алгоритм может предсказать сложность времени произвольной входной программы?

Проблема Halting гласит, что невозможно написать программу, которая может определить, останавливается ли другая программа, для всех возможных программ ввода .

Тем не менее, я могу, конечно, написать программу, которая может вычислить время выполнения программы вроде:

for(i=0; i<N; i++)
    { x = 1; }

и вернуть временную сложность , даже не запуская ее.$N$

Для всех других программ ввода он возвращает флаг, указывающий, что он не может определить сложность времени.

У меня вопрос такой:

Какие условия должны выполняться, чтобы мы могли алгоритмически определить временную сложность данной программы?

* Если на это есть каноническая ссылка или обзорная статья, я буду признателен за ссылку в комментариях.

В общем, вы не можете определить сложность, даже для остановки программ: пусть будет некоторой произвольной машиной Тьюринга, и пусть p T будет программой (которая всегда возвращает 0):$T$$p_T$

input: n
run T for n steps
if T is in halting state, output: 0
otherwise, loop for n^2 steps and output: 0

Ясно, что в общем случае неразрешимо, является ли линейным или квадратичным временем.$p_T$

Тем не менее, была проведена большая работа по эффективному вычислению сложности программы. У меня есть особая любовь к теории неявной сложности, которая направлена ​​на создание языков, которые, используя специальные конструкции или типовые дисциплины, позволяют писать только программы, которые живут в определенном четко определенном классе сложности. То, что я считаю чудом, эти языки часто являются законченными для этого класса!

Один особенно хороший пример описан в этой статье J.-Y. Марион, которая описывает крошечный императивный язык, с типом дисциплиной вдохновленной от методов информационно-потоков и анализа безопасности, что позволяет характеристику алгоритмов P .

Вопрос, который вы задаете, и конкретный подсчет, который вы описываете, является классическим при анализе программ. Существует теоретическая проблема анализа сложности, и это практическое проявление в терминах автоматической оценки производительности фрагмента кода. Такой автоматический анализ имеет несколько приложений, от обнаружения ошибок производительности до оценки стоимости некоторых вычислений в облаке.

Коди отметил, что проблема в общем неразрешима. Эта проблема сложнее, чем доказательство завершения, потому что получение границы сложности влечет за собой то, что программа также завершается. Есть два подхода к такой проблеме. Один из анализа программы. Идея добавления счетчика и оценки его стоимости существует с 70-х годов. Это кодирование сводит проблему определения времени выполнения к вычислению инварианта.

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

Ниже приведены некоторые ссылки для обеих областей.

1. Проект SPEED - это одна из конкретных линий анализа программы, которая фокусируется на том, как найти границы на счетчиках после их введения в программу. Счетчики могут измерять время или пространство.
2. Многофакторный амортизированный анализ ресурсов , Ян Хоффман, Клаус Элиг, Мартин Хоффман, ACM TOPLAS 2012
3. О разрешимых скоростных свойствах императивных программ , Амир Бен Амрам, «Разработки в неявной вычислительной сложности 2010». Это прекрасная работа по ограничению сложности императивных программ синтаксическими ограничениями.