Прикладная теория кодирования

О проблеме декодирования по принципу максимального правдоподобия

В. Ю. Попов

Уральский федеральный университет имени первого Президента России Б. Н. Ельцина, г. Екатеринбург, Россия

Аннотация: Рассмотрен количественный аналог проблемы декодирования по принципу максимального правдоподобия. Установлена экономная сводимость от проблемы совершенного паросочетания и слабо экономная сводимость от проблемы максимального разреза. Показана полнота в классах WPP, C$_=$P и PP для некоторых количественных вариантов проблемы декодирования по принципу максимального правдоподобия.

Ключевые слова: вычислительная сложность, проблема декодирования по принципу максимального правдоподобия, проблема совершенного паросочетания, проблема максимального разреза.

УДК: 510.52

DOI: 10.17223/20710410/70/1