51 585
редагувань
Відмінності між версіями «Тест простоти»
м
→Складність: послався на ізольовану (Co-NP)
Олюсь (обговорення | внесок) м |
Aeou (обговорення | внесок) м (→Складність: послався на ізольовану (Co-NP)) |
||
|
== Складність ==
У [[теорія складності обчислень|теорії складності обчислень]], формальну мову, яка відповідає простим числам, позначають PRIMES. Неважко показати, що PRIMES належить до '''
У 1975 [[Вауган Пратт]] показав існування сертифікату простоти, який перевіряється за поліноміальний час, і значить PRIMES належить до [[NP (складність)|NP]], а тому й до '''NP ? coNP'''. Деталі дивись у [[сертифікат простоти]].
Подальше відкриття алгоритмів Соловея-Штрассена та Міллера-Рабіна показало належність PRIMES до [[RP (складність)|coRP]]. У 1992 алгоритм Адлемана-Хуанга звузив складність до [[ZPP]] = '''RP''' ? '''coRP''', що є заміщенням результату Пратта.
Циклотомічний тест Адлемана, [[Померанце]] та Рамлі
Існування [[AKS тест простоти|AKS тесту простоти]], який остаточно розв'язав цю давню проблему, означає, що PRIMES належить до [[P (складність)|P]].
| |||