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