Многие классы сложности имеют «полные» проблемы. Существуют ли полные задачи для класса сложности задач, которые можно решить за времени?
Сложность состоит в том, что этот класс зависит от модели вычислений; проблема может быть решена за раз в одной разумной модели вычислений, но не в другой, учитывая, что «разумный» обычно означает эквивалентность за полиномиальное время с машиной Тьюринга. Тем не менее, он все еще может быть разработан для конкретных разумных моделей.
Я думаю, что имеет смысл взглянуть на постоянные сокращения много-один. Тем не менее, я также открыт для рассмотрения других разумных сокращений, если есть литература по ним.
Существует ли что-нибудь подобное для какой-либо модели вычислений?
источник
Я думаю, что для задач все языки завершены в «сокращениях с постоянным временем», кроме иL = Σ ∗ L = ∅O(1) L=Σ∗ L=∅
Предположим, что иL ≠ 0 , L ≠ Σ ∗L , L'∈ O ( 1 ) L ≠ 0 , L ≠ Σ*
ПустьИксY∈ L , xN∉ L
Это постоянное сокращение времени от до : LL' L
Итак, полон для (... ленивое сокращение, ленивый результат :-)).L O ( 1 )
источник