Сложные задачиИдеиm=2^nОценкиНижниеТочно сложные?НеприближаемыеAPX-полнотаPCP-теоремаСложно точное решениеДМТPSPACE-полнотаNP-полнотаNP≠Not PS=VTВМТBPPRPPТеория сложностиВерхниеОценкиАсимптотическиеДля почти всехне помнят нихренаВ среднемПолиномиальный в среднем для SATне было?Упаковкане помнят\Алгоритм Немхаузера-УльманаСтарых детерминированныхАлгоритмыПриближенно-вероятностныеFPRASПодсчет выполняющих наборов для ДНФне было?ВероятностныеМонте-КарлоПолиномыФрейвалдВероятностное округлениеMAX-CUTне было?MAX-SATничего не помнимМаксимум скобокКНФконьюнкцияскобоклитераловотрицаниепеременнаядизьюнкцияПриближенныеДерандомизацияМетод малых вероятностных пространствне былоMAX-SATне было?Гарантированная точностьэпсилон-оптимальностьPTASFPTASрюкзакO(n^2/eps)poly(n, 1/eps)?посмотреть что1+epsконстантная3/2Кристофидеса2Вершинное Покрытиемодифицированный жадныйO(log n)Задача покрытииЭвристикиЖадный рюкзакТочныеПолиномиальныеO(N^100)2001PRIME in PO(n^6)O(n^11)Одностороння функцияДискретный логарифмЭль гамальNPC-полные задачиРюкзачные схемыФакторизацияRSAO(N^4)квадратичныеO(NlogN)линейные