Seminars: V. V. Podolskii, Занятие 4. Класс NP, примеры. Соотношение с классами P и PSPACE. Недетерминированные машины Тьюринга, второе определение класса NP, эквивалентность определений. Полиномиальные сводимости, их основные свойства. NP-трудность и NP-полнота, их основные свойства

Seminars

RUS ENG

JOURNALS PEOPLE ORGANISATIONS CONFERENCES SEMINARS VIDEO LIBRARY PACKAGE AMSBIB

JavaScript is disabled in your browser. Please switch it on to enable full functionality of the website

	Calendar
	Search
	Add a seminar

	RSS
	Forthcoming seminars

Introduction to computational complexity theory
October 13, 2020 16:15, Moscow, MIPT - MI RAS

Занятие 4. Класс NP, примеры. Соотношение с классами P и PSPACE. Недетерминированные машины Тьюринга, второе определение класса NP, эквивалентность определений. Полиномиальные сводимости, их основные свойства. NP-трудность и NP-полнота, их основные свойства

V. V. Podolskii

*Video records:*
	MP4	242.7 Mb

Number of views:
This page:	145
Video files:	40

Registration to the website

Logotypes