Монография содержит систематическое изложение важнейших аспектов теории сложности вычислений. Ее автор - известный американский ученый, крупный специалист в области теории сложности и ее приложений. В книге на высоком научном уровне последовательно и во взаимосвязи рассмотрены основные модели вычислений: схемы, формулы, последовательностные машины (автоматы), машины Тьюринга и др. Обсуждаются такие темы, как сети сортировки, сложность умножения матриц и NP-полные проблемы. Большой интерес представляет предложенный автором подход к описанию работы реальных ЭВМ, основанный на моделях и методах теории сложности. Особое внимание уделено выводу вычислительных неравенств, связывающих сложность вычислений на различных моделях. Книга содержит большое количество задач и упражнений различного уровня сложности.
Книга предназначена для специалистов в области дискретной математики и математической кибернетики, информатики и вычислительной техники, аспирантов и студентов соответствующих специальностей; она будет также полезна всем, интересующимся этими областями знания. Это и многое другое вы найдете в книге Сложность вычислений (Джон Э. Сэвидж)