Сложность вычислений ФПМИ

Задачи на обе темы в любом случае будут, просто какие-то в этой контрольной, а какие-то в следующей.

Какие задачи включить в контрольную? Про полиномиальную иерархию (классификация и полнота на каком-то уровне) – 18 👍👍👍👍👍👍👍 67% Про классы L и NL – 9 👍👍👍👍 33% 👥 27 people voted so far.

Сейчас здесь появятся листочки с задачами первых 4 семинаров.

Также на странице курса вывешена и будет обновляться книга конспектов - http://ru.discrete-mathematics.org/fall2017/3/complexity/compl-book.pdf Решения некоторых задач там приведены.

https://docs.google.com/spreadsheets/d/12-3WWCwysKpsEpiPkaGdwwnQg2rNoCWa98ZA6jAjiSc/edit?usp=sharing - форма для выбора темы. Форма открытая, пожалуйста, обойдитесь без вандализма. Внизу есть табличка с количеством выбравших каждый проект, контролируйте, чтобы число по каждому проекту не превышало двух.

Наконец вывешен список тем для проектов. Если не понравится выбор, придумайте свою.

Это обновлённая глава про вычислительные модели из будущей книги. Будут ещё добавлены исторический раздел и задачи. Там же есть решение задачи про палиндром.

Со следующего понедельника начинается спецкурс Б.З.Мороза "Диофантовы уравнения". Начало в 18:30, аудитория 419 ГК. Аннотация: Цель этого спецкурса — доказать теорему Ю.В. Матиясевича о диофантовости перечислимых множеств. Из этой теоремы. в частности, следует существование полинома от многих переменных с целыми рациональными коэффициентами, множество положительных значений которого есть множество простых чисел. Разумеется, такого полинома от одной переменной не существует (упражнение !). Теория диофантовых уравнеий — старая и вечно новая область чистой математики. Теорема Матиясевича показывает, что любая (точно поставленная) математическая задача в принципе сводится к поиску решений некоторого диофантова уравнения. Никаких специальных знаний от слушателей курса не предполагается.

Ссылка для присоединения к чату для желающих: https://t.me/joinchat/DZlFTUSE1txDQid4LeIkbA