О генерической сложности проблемы декодирования линейных кодов

Изучается генерическая сложность проблемы декодирования линейных кодов. Эта проблема лежит в основе известной криптосистемы Мак-Эллиса. Доказывается, что её естественная подпроблема генерически трудноразрешима (то есть трудна для почти всех входов) при условии, что проблема декодирования линейных кодов трудноразрешима в классическом смысле.