Поговорим о сложности. Немного вышедшая из моды тема "P vs NP ". О чем же идет речь? Многие задачи сводятся к перебору на конечном множестве. Скажем, поиск или сортировка. И разные алгоритмы имеют различную сложность, то есть число операций из заданного набора допустимых операций. Например, команд процессора или (в случае сортировки) сравнений. Вот есть сортировка методом пузырька: каждый элемент сравнивается с соседними и меняется с ними местами, если надо. Как бы всплывает. А есть более эффективные алгоритмы, например QuickSort...

Рассматриваются некоторые результаты, полученные, используя аксиому спуска для бинарных математических утверждений [ 1 ]. Далее, рассматривается счетный класс неориентированных графов с нечетным числом вершин. Проблема отыскания всех простых путей в графе при рассмотрении, что они проходят через все вершины, графа формулируется и решается. Мы доказываем, что число таких путей является неполиномиальным множеством для достаточно большого числа вершин графа. Мы показываем как преобразовать такой граф в гамильтоновый граф с добавлением единственного ребра; и доказываем, что вероятность распознавания гамильтоновой природы такого графа стремится к нулю с неограниченным ростом числа вершин графа...