In some curved spaces, one can solve NP-hard problems in polynomial time

В конце 1970-х и в начале 1980-х годов Ю. В. Матиясевич написал серию статей о возможности решения NP-трудных задач за полиномиальное время. В этих статьях он предложил несколько схем, использующих различные физические явления и инженерные конструкции для параллелизации вычислений. В настоящей статье мы рассматриваем одну из таких схем: параллельные вычисления в искривленном пространстве. Библ. – 50 назв.