Czy problemy PRIMES, FACTORING są znane jako P-hard?

Niech PRIMES (inaczej testowanie pierwotności ) będzie problemem:

Biorąc pod uwagę liczbę naturalną , czy jest liczbą pierwszą? $n$ $n$

Niech FACTORING będzie problemem:

Biorąc pod uwagę liczby naturalne , przy , czy ma współczynnik przy ? $n$ $m$ $1 \leq m \leq n$ $n$ $d$ $1 < d < m$

Czy wiadomo, czy PRIMES jest P-twardy? Co powiesz na FAKTORING? Jakie są najbardziej znane dolne granice dla tych problemów?

— km
źródło

Nie, IIRC jest otwarty, jeśli liczba pierwsza jest twarda P. Myślę, że to samo dotyczy FACTORING.

— Kaveh

Wydaje mi się, że alternatywnym pytaniem może być: czy są jakieś konsekwencje dla PRIMES lub FACTORING bycia twardym?

— Suresh Venkat

@Suresh: to miłe pytanie. Czy możesz to opublikować osobno?

— András Salamon,

Właściwie to już zostało poproszone o faktoring: cstheory.stackexchange.com/questions/5096/…

— Suresh Venkat

@Artem, zgadzam się z András, pytanie o konsekwencje P-twardości liczb pierwszych byłoby interesujące. Zredagowałem to pytanie, dodając pytanie o najbardziej znane dolne krawędzie.

— Kaveh

$\mathsf{TC^0}$

— Eric Allender
źródło

\frac{1}{n}

$\frac1 n$

n

$n$

A C C^{0}

$ACC^0$