Pytania otagowane jako p-hardness

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 n jest liczbą pierwszą?nnnnnn Niech FACTORING będzie problemem: Biorąc pod uwagę liczby naturalne , m przy 1 ≤ m ≤ n , czy n ma współczynnik d przy 1 < d < m ?nnnmmm1≤m≤n1≤m≤n1 \leq …

39 cc.complexity-theory lower-bounds factoring primes p-hardness

P-pełne problemy na drzewach

To pytanie jest związane z jednym z moich wcześniejszych pytań, trudnymi NP na drzewach . Szukam problemów, które są kompletne P na drzewach.

14 cc.complexity-theory graph-theory tree p-hardness

Gęstość języków P-zupełnych

Załóżmy, że jest językiem boolowskim o skończonych łańcuchach ponad . Niech będzie liczbą łańcuchów w o długości . Dla funkcji od dodatnich liczb całkowitych do dodatnich liczb rzeczywistych, ma górną gęstość jeśli dla wszystkich wystarczająco dużych .L.L.LL n L n d ( n ) L d ( n ) L …

10 cc.complexity-theory reference-request p-hardness

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.