City: Test Saint Petersburg Novosibirsk Kazan Language: Русский English

Лекция 2. Короткие доказательства и класс NP
Introduction to Theoretical Computer Science

What: Lecture
When: Monday, 21 September 2020, 18:30–19:50
Where: Конференция в zoom, Онлайн

Description

Эффективные системы доказательств. Класс NP. Критерий Пратта и доказательство простоты числа. Класс P. Сведения, полные задачи. NP-полнота задачи об ограниченной остановке. Булевы схемы. Сведение Circuit-SAT к 3SAT.

Video

Other materials

Текущая версия конспекта.