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,

F A C T O R = {(m, r) : \exists s such that 1 < s < r and s divides m}

$FACTOR = \{(m,r) :\;\; \exists s \text{ such that} 1<s<r \text{ and } s \text{ 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)? $NP \cap Co-NP$ $NP$ $m$ $r$

complexity-theory factoring

— Fequish
źródło

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

2

zobacz także NP kompletny wariant faktoringu / Informatyka teoretyczna

— od

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 . $m$ $r$ $m$ $m$ $r$

— Yuval Filmus
źródło

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ą).

e^{O ((\log n)^{1 / 3} (\log \log n)^{2 / 3})}

$e^{O((\log n)^{1/3}(\log\log n)^{2/3})}$

n

$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.

— Denis Pankratov
źródło

3

Certyfikaty Pratt na Wikipedii

— Kaveh