Язык, который является RE полным в отношении сокращений полиномиальных времен?

Question

Есть ли какой-либо язык в RE, который является полным в отношении сокращений полиномиального времени?

Я думаю, что A_TM будет хороший пример, но я не уверен ...

Answer 1

Да, A _TM является RE -полное относительно сокращения полиномиальное время. Для любого RE язык L, пусть M - распознаватель для него. Тогда функция f (w) = может быть вычислена в полиномиальное время (для некоторого разумного представления кортежей), так как M является фиксированной машиной, а длина w в кодированной версии должна быть не более чем на полиномиальном уровне, чем исходный вход w. У нас также есть, что ж ∈ L тогда и только тогда, когда M принимает ж тогда и только тогда, когда ∈ _TM, так е является сокращение полиномиальное время от произвольного RE языка L для A _ТМ, делая _TMRE -полный относительно сокращений полиномиального времени.

Я не знаю, почему вы были бы заинтересованы в данном понятии RE -полноты, так как RE в основном используется для представления о вычислимости (вы можете решить эту проблему вообще?), А сокращения полиномиальных времен, как правило, для сложности (можете ли вы решить эту проблему эффективно?) Если у вас есть интересный прецедент для них, я бы хотел услышать об этом!