Является ли класс функций поли-времени рекурсивно перечислимым?

Question

Если я определяю функции Poly-time, то функции, которые вычисляются машиной Тьюринга за максимальное полиномиальное (n) время, n - это размер входных данных.Является ли класс этих функций рекурсивно перечислимым?

Answer 1

Сравнительно легко дать перечисление для всех функций, вычислимых за полиномиальное время: просто дать перечисление pi_j для всех полиномов, для j в N, а затем рассмотреть для любой пары (i, j) машину, которая работает как Машина Тьюринга M_i с часами pi_j. Любая функция, вычислимая за полиномиальное время, может быть выражена таким образом.

Это сильно отличается от проблемы, чтобы понять, работает ли универсальная машина Тьюринга за полиномиальное время, это не решаемо. Доказательство не совсем тривиально, так как оно не является экстенсиональным свойством программ, и мы не можем применить теорему Райса. Вы можете найти доказательство в моей статье «Интенциональное содержание теоремы Райс», POPL 2008 (жемчужина).

Проблема обеспечения синтаксических характеристик классов рекурсивной сложности, таких как P, Pspace и т. Д., Получила большое внимание в литературе. Недавняя область неявной сложности направлена ​​на изучение вычислительной сложности программ без ссылки на конкретную модель машины и явных ограничений времени или памяти, но вместо этого полагается на логические или вычислительные принципы, которые влекут за собой свойства сложности, обычно посредством контролируемого использования доступные ресурсы. Для введения в эту тему вы можете обратиться к специальному выпуску по неявной вычислительной сложности, ACM Trans. Вычи. Log., Vol 10, n.4 2009.

Были получены другие интересные характеристики, ограничивающие интерпретация языков программирования в конечных областях. Семенной Результатом в этой области является старая работа Гуревича («Алгебры выполнимых функций», FOCS 1983), где он доказал, что при интерпретации примитивно-рекурсивных функций (соответственно, рекурсивных функций) над конечными структурами точно получается лог-пространство (соответственно, за полиномиальное время ) вычислимые функции.

Пожалуйста, ознакомьтесь с моей статьей "Вычислительная сложность через конечные типы", ACM Trans. Вычи. Log., Vol 16, n.15 2015, для большего количества ссылок в этом область.

Answer 2

Ну, ответ вроде бы нет, взгляните на диаграмму в Сложность класса .

Answer 3

Ответ - да, на самом деле я также нашел доказательство в книге. Спасибо всем, мне очень помогли данные указания:)

Answer 4

Я почти уверен, что ответ - нет.Программа для рекурсивного перечисления функций Poly-time должна в какой-то момент сказать вам, является ли функция, которая решает задачу коммивояжера, Poly-time.Вопрос о том, отвечает ли этот конкретный вопрос в настоящее время, пока открыт.

Я не знаю, что я курил с этим ужасным ответом.Если проблема коммивояжера не в Poly-time, программа никогда не должна обнаруживать этот факт.Просто никогда не обходится перечислением каких-либо решений для этого.Что легко, потому что он никогда не найдет его.

Одна важная деталь, которая мне не ясна, это то, как вы представляете функции и что вы считаете уникальной функцией.

Предположим, что функция равна,«Программа, которая работает в Poly-time», и вы хотите перечислить все программы, независимо от того, производят ли они одинаковый вывод. Тогда ваш ответ сводится к: «Если для данной программы используется Poly-time, всегда есть доказательствоэтот факт?Это явно неверно.У вас может быть программа, которая ищет многозначительное время для доказательства какого-либо открытого вопроса, и, если оно находит его, оно тратит экспоненциальное время, прежде чем получить окончательный результат.В этой программе много времени, но вы не можете доказать это, не доказав, что открытый вопрос - ложь.

Предположим, что эта функция для вас равна «правилу, которое связывает входы с выходами», и вы не согласны ссписок нескольких программ, которые кодируют одну и ту же функцию.Давайте изменим предыдущую патологическую функцию, чтобы модифицировать ее вывод, а не тратить время, если упомянутое доказательство было обнаружено.Теперь вы можете доказать, что эта программа работает по разному времени, но вы не можете доказать, представляет ли она функцию, отличную от той, которая не выполняет весь этап проверки (и, возможно, не изменяет свой вывод).

Предположим, чтодля вас функция равна «правило, которое связывает входы с выходами», и вы в порядке с перечислением нескольких программ, которые кодируют одну и ту же функцию, но не хотят каждую.Предположим, что prog - это программа, которая может быть или не быть поли-временем, а p(x) - это полином.Легко написать вторую программу, которая эмулирует первую для шагов p(x), а если другая все еще работает, выдает какой-то фиксированный вывод.Эта вторая программа гарантированно будет поли времени.Если на самом деле prog является поли-временем, то некоторая программа этой формы будет представлять ту же функцию, что и prog, и поэтому список выходных данных будет включать все возможные поли-функции.(Но одна и та же функция будет закодирована разными способами.)