Dlaczego FACTOR w Co-NP?


12

Mam problem z obejściem problemów PRIME, COMPOSITE, FACTOR i ich powiązania pod względem złożoności. Rozumiem, że PRIME wykazał, że jest w w teście pierwotności AKS i uważam, że działa to również w przypadku KOMPOZYTU.P

Jeśli chodzi o CZYNNIK,

FACTOR={(m,r):s such that1<s<r and s divides m}

z tego co przeczytałem wydaje się, że jest w . Widzę, że jest w ponieważ certyfikat składałby się z głównego dzielnika mniejszego niż . Ale jaki rodzaj certyfikatu może wykazać, że nie ma takiego głównego dzielnika (w czasie wielomianowym)?N P m rNPCoNPNPmr


1
Aby język był w dowodzie NP, że dane wejściowe należą do języka, musi on posiadać certyfikat, który można zweryfikować w czasie wielomianowym. Nie oznacza to, że istnieje certyfikat dla danych wejściowych nienależących do języka, który można skutecznie zweryfikować.
sashas

Odpowiedzi:


11

Zaświadczeniem, że nie ma nietrywialnego dzielnika mniejszego niż jest faktoryzacja . Możemy sprawdzić w czasie wielomianowym, czy wszystkie czynniki są rzeczywiście pierwsze (ponieważ pierwotność jest w P za pomocą testu pierwotności AKS ), czy ich iloczyn jest , a wszystkie z nich są co najmniej .r m m rmrmmr


1
Dziękuję Ci. I czy dobrze rozumiem, że algorytm AKS może powiedzieć nam, czy liczba jest liczbą pierwszą w czasie wielomianowym, ale jeśli nie jest liczbą pierwszą, nie podaje nam czynników?
Fequish

1
@Fequish: Jeśli nie jest liczbą pierwszą, AKS nie podaje nam czynników.

2
Faktoring nie jest znany jako wykonalny w czasie wielomianowym. Najlepszy znany algorytm ma złożoność heurystyczną (tutaj jest samą liczbą). NeO((logn)1/3(loglogn)2/3)n
Yuval Filmus

5

Aby dodać do odpowiedzi Yuvala: w 2002 r. Odkryto testy pierwotności AKS. Wcześniej nie dysponowaliśmy algorytmem wielomianowym do sprawdzania, czy liczba jest liczbą pierwszą. Jednak Pratt odkrył w 1975 r., Co jest obecnie znane jako certyfikaty Pratt dla pierwotności i udowodnił, że Primes jest w NP. Możemy dołączyć te certyfikaty pierwotności Pratta dla czynników w naszym certyfikacie, aby pokazać, że WSPÓŁCZYNNIK znajduje się w koNP zamiast używać algorytmu AKS w celu sprawdzenia, czy czynniki są pierwotne bezpośrednio.


Korzystając z naszej strony potwierdzasz, że przeczytałeś(-aś) i rozumiesz nasze zasady używania plików cookie i zasady ochrony prywatności.
Licensed under cc by-sa 3.0 with attribution required.