У меня возникают проблемы, когда я обдумываю проблемы ПРАЙМ, КОМПОЗИТ, ФАКТОР и их взаимосвязь с точки зрения сложности. Я понимаю, что PRIME был показан в тестом на примитивность AKS, и я считаю, что это работает и для COMPOSITE.
Что касается ФАКТОРА,
от того, что я читал, кажется , что он находится в . Я вижу, что это в N P, так как сертификат будет состоять из простого делителя m меньше чем r . Но какой сертификат может установить, что такого простого делителя не существует (за полиномиальное время)?
complexity-theory
factoring
Fequish
источник
источник
Ответы:
источник
В дополнение к ответу Ювала: тестирование простоты AKS было открыто в 2002 году. До этого у нас не было алгоритма полиномиального времени, чтобы проверить, является ли число простым. Однако в 1975 году Пратт обнаружил то, что сейчас известно как свидетельство Пратта о первичности, и доказал, что Прим находится в NP. Мы можем включить эти сертификаты первичности Pratt для факторов в нашем сертификате, чтобы показать, что FACTOR находится в coNP вместо использования алгоритма AKS, чтобы проверить, являются ли факторы первичными непосредственно.
источник