Відмінності між версіями «Тест простоти»

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

редагувань