Большая техническая энциклопедия
2 4 7
D L N
А Б В Г Д Е Ж З И Й К Л М Н О П Р С Т У Ф Х Ц Ч Ш Щ Э Ю Я
ВА ВБ ВВ ВЕ ВЗ ВИ ВК ВЛ ВН ВО ВП ВР ВС ВТ ВУ ВФ ВХ ВЫ ВЯ

Валиант

 
Валиант [18] обнаружил, что синтаксический анализ столь же сложен, как и умножение булевых матриц. Следовательно, поскольку Iog272 81, справедлива следующая теорема.
Валиант дал много примеров фР - полноты функций, но, возможно, наиболее интересный из них - перманент целочисленной матрицы.
Валиант дал первое убедительное объяснение этой безуспешности, когда доказал, что перманент фР - полон.
Есть, однако, большое количество очевидно невычислимых функций, для которых, по-видимому, нельзя найти никакого доказательства AfP-полно-ты, к ним применимого. Лесли Валиант [86, 87], чтобы выйти из положения, ввел понятие фР - полноты.
Пиппенджер и Валиант [8] сумели доказать для некоторых систем монотонных функций наподобие системы функций сортировки и булевой свертки, что любая монотонная схема, реализующая такую систему, должна представляться сдвигающим графом ( a shifting graph), и поэтому должна содержать Q ( nlogn) элементов по числу Q ( ttlogn) вершин графа.
 
Loading
на заглавную 10 самыхСловариО сайтеОбратная связь к началу страницы

© 2008 - 2014
словарь online
словарь
одноклассники
XHTML | CSS
Лицензиар ngpedia.ru
1.8.11