Universal Memcomputing Machines
Memcomputing NP-complete problems in polynomial time using polynomial resources and collective states
A review of “Memcomputing NP-complete problems in polynomial time using polynomial resources”
В первой статье авторы утверждают, что мемкомпьютеры по вычислительной мощности эквивалентны недетерминированной машине Тьюринга. Во второй — приводят реальный компьютер с 6-ю мемпроцессорами, способный решить задачу "Сумма подмножества" с 6-ю числами. Компы с большми кол-вом мемпроцессоров наталкиваются на проблему шума и, возможно, это тупиковое направление. Однако, авторы утверждают, что это проблема только данной реализации и возможна реализация, решающая NP-полные задачи за полиномиальное время.
Интересно было бы увидеть комп, решающий за разумное время задачу хотя бы со 100 числами примерно по 2^100 каждое. Впрочем, для математика и этого мало — нужно еще доказательство, что такое же время решения будет и для "самого плохого" набора чисел.
Программировать сложно. Но не программировать еще сложнее.