Описанное сведение

Cтраница 1

Описанное сведение можно осуществлять и в случае алфавитных операторов, у которых входной и выходной алфавиты различны. Например, пусть ф - произвольный алфавитный оператор с входным алфавитом А и выходным алфавитом С, В - стандартный алфавит, а - какое-либо ( обратимое) кодирование слов в алфавите А словами в стандартном алфавите, а у - аналогичное кодирование слов в алфавите С. [1]

Описанное сведение задачи А к задаче В является, таким образом, псевдополиномиальным. [2]

Построение описанного сведения требует выполнения не более 0 ( ( v - - e) e) операций. [3]

Реализация описанного сведения требует выполнения не более O ( v e) операций. [4]

Построение описанного сведения требует выполнения не более 0 ( ( у е) 2) операций. [5]

Реализация описанного сведения требует выполнения 0 ( п) операций. [6]

Реализация описанного сведения требует выполнения О ( 2 tA операций. [7]

Реализация описанного сведения требует выполнения О ( nl) операций. Это сведение является и полиномиальным, и ( что легко проверить) псевдополиномиальным. [8]

Реализация описанного сведения требует выполнения 0 ( т) операций. Это сведение является как полиномиальным, так и псевдополиномиальным, и задача 2.2, з) является, следовательно, ЛФ-трудной в сильном смысле. [9]

Построение описанного сведения требует выполнения не более О ( raj) операций. Поскольку задача о 3-разбиении ЖР-полна в сильном смысле, задача 2.3 является ЖР-трудной в сильном смысле. [10]

Построение описанного сведения требует выполнения 0 ( п0) операций. Поскольку задача о 3-разбиении ЛФ-пол-на в сильном смысле, задача 2.4, а) является / VP-трудной в сильном смысле. [11]

Поверхностное натяжение при 71 С. [12]

Располагая описанными сведениями о факторах, влияющих на смещение точки начала фазового перехода, рассмотрим, как будет происходить процесс снижения давления в нефтяной и газоконденсатнои залежах. [13]

Для реализации описанного сведения достаточно выполнить 0 ( п) операций. [14]

Нетрудно заметить, что реализация описанного сведения требует выполнения 0 ( па) операций и что это сведение является одновременно и полиномиальным, и псевдополиномиальным. Из того, что задача о 3-разбиении является ЛФ-полной в сильном смысле, следует, что задача 2.1, а) является ЛФ-трудной в сильном смысле. [15]

Страницы: 1 2