Приводит ли Карп сводимость к полному порядку?

15

Или, другими словами, у нас есть это для каждого языка и , или ?B A p B B p AAВAпВВпA

Мал
источник

Ответы:

27

Отнюдь не. В самом деле, любая исчисляемая дистрибутивная решетка встраивается как субчастичный порядок , даже если мы рассматриваем эти степени только между двумя заданными фиксированными языками ( К. Амбос-Шпионы, Подрешетки полиномиальных степеней времени , Информ. & Контроль 65). (1): 63-84, 1985).п

Джошуа Грохов
источник
1

В качестве тривиального контрпримера можно рассмотреть и B = { 0 , 1 } . Ни то, ни другое не сводимо к другому, поскольку x A всегда неверно, а y B всегда верно.A=Взнак равно{0,1}*ИксAYВ

Даниил Мусатов
источник