Изучаются две модели вычислимости над произвольной алгебраической системой U = (А, σ): 1) вычислимость над списочной надстройкой, предложенная И. В. Ашаевым, В. Я. Беляевым и А. Г. Мясниковым, и 2) S-вычислимость А. Хеммерлинга. Доказывается полиномиальная эквивалентность этих моделей для множества строк А+ над основным множеством A алгебраической системы U. Это означает, что любая функция f : А+ → А+, вычислимая за полиномиальное время в S-вычислимости, также вычислима за полиномиальное время над списочной надстройкой, и наоборот. В частности, это показывает, что аналоги класса сложности Р в этих двух моделях над строками А+ совпадают. То же самое имеет место и для аналогов класса NP. Полученные результаты можно использовать для оценки вычислительной сложности различных алгоритмов, написанных на языках программирования высокого уровня.
1 Visitors
1 Hits
0 Downloads
