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

Связь нижних оценок на графовую сложность с задачей P vs NP (И. Михайлин)
Boolean Functions Complexity

What: Lecture
When: Sunday, 23 October 2011, 13:00–14:35
Where: ПОМИ РАН
Slides: boolean_functions_complexity_lecture_231011.pdf

Description

Связь между графами и схемами, различные способы представить граф схемой: показательная и характеристическая схемы. P\( \neq \)NP как следствие нижней оценки \( (12+\varepsilon)n \) на графовую сложность.

Attached files