Существуют ли «O (1) -полные» проблемы?

9

Многие классы сложности имеют «полные» проблемы. Существуют ли полные задачи для класса сложности задач, которые можно решить за времени?O(1)

Сложность состоит в том, что этот класс зависит от модели вычислений; проблема может быть решена за раз в одной разумной модели вычислений, но не в другой, учитывая, что «разумный» обычно означает эквивалентность за полиномиальное время с машиной Тьюринга. Тем не менее, он все еще может быть разработан для конкретных разумных моделей.O(1)

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

Существует ли что-нибудь подобное для какой-либо модели вычислений?

Майк Батталья
источник

Ответы:

3

Поскольку чтение входных данных необходимо почти для всех проблем, нам нужно как минимум время для почти всех задач, где - размер входных данных. Поэтому вы можете подумать о классе линейных временных проблем, который уже определен.nΩ(N)N

Однако мы до сих пор не знаем ни -полной, ни -полной проблемы. Поле мелкозернистой сложности имеет некоторые новые результаты в этой области, но классы основаны на проблемах (например, APSP эквивалентен Radius, Negative Triangle, ...).O ( n 2 )О(N)О(N2)

Mohemnist
источник
Я не уверен, отвечает ли это на вопрос. Многие проблемы требуют времени , но не все из них - все еще есть некоторые проблемы, которые можно решить за время - поэтому кажется, что заданный вопрос остается актуальным. O ( 1 )Ω(N)О(1)
DW
1
Это также предполагает, что входные данные должны читаться последовательно, и нет никакого косвенного обращения, так что это будет один из тех случаев, когда модель действительно имеет значение. (Мне интересно, стоит ли мне настаивать на непрямости и, возможно, случайности в моем первоначальном посте, иначе вы
Майк Батталья
Проблема, чтобы решить, если что-либо дано как ввод, занимает время. Все другие задачи, которые занимают постоянное время, являются ограниченными постоянными версиями других задач. О(1)
rus9384
Что именно вы подразумеваете под «ограниченными постоянными версиями других задач»?
Майк Батталья
@MikeBattaglia, например, если машина Тьюринга остановится после выполнения 100 шагов.
rus9384
2

Я думаю, что для задач все языки завершены в «сокращениях с постоянным временем», кроме иL = Σ L = O(1)L=ΣL=

Предположим, что иL 0 , L Σ L,L'О(1)L0,LΣ*

ПустьИксYL,ИксNL

Это постоянное сокращение времени от до : LL'L

  • заданный решить в разИксL'О(1)
  • если выведите , иначе выведитеИксL'ИксYИксN

Итак, полон для (... ленивое сокращение, ленивый результат :-)).LО(1)

Вор
источник
1
В общем, жесткость для класса не осмысленно определена для сокращений , которые являются столь же мощным , как самого, именно по той причине , вы заявили. Чтобы иметь полное определение TIME ( ) -полного, нам нужны сокращения, которые слабее, чем постоянное время. Я не знаю, что это может быть. CCO(1)
Понт
@Pontus: я согласен; и определенно не так интересно ... если только мы не живем в дискретной и конечной вселенной :-D
Vor
... мы могли бы использовать уменьшение шагов ( фиксированное ), но в этом случае нет полных проблем ... или добавить ограничение между размером ТМ и количеством постоянных шагов (например, если размер ( детерминистический / недетерминированный) TM равен тогда допускается только шага) ...ККNN/2
Vor
Да, возможно, что-то интересное может (или было) придумано. Что такое ТМ в вашем последнем предложении?
Понт
@Vor Как насчет фиксированной ширины постоянной времени в некоторой параллельной модели?
l4m2