Декодирование при помощи линейных программ: различия между версиями

Еще один интересный вопрос – существуют ли семейства кодов с линейным расстоянием и постоянной скоростью, для точного декодирования которых можно разработать линейные программы полиномиального размера. Другими словами, есть ли семейства кодов с описанными характеристиками, выпуклые обочки которых имеют полиномиальное число граней? Если да, то для такого семейства LP-декодирование будет эквивалентно ML-декодированию. Если нет, то это служит убедительным доказательством распространенного мнения, заключающегося в том, что субоптимальное декодирование при использовании хороших кодов неизбежно.