Re: Re: Liczby pierwsze. Pytania euklidowskie.

Michal Przybylek <mrp@neostrada.pl> napisał: 

> Dnia 05-06-2008 o 08:26:16 Wlodzimierz Holsztynski  
> <guru_ji.SKASUJ@gazeta.pl> napisał:
> 
> > Dodam problem informatyczny.
> > Bezpośrednie liczenie P(n)
> > wymaga liczenia aż 2^n różnych
> > różnic (przy czym złożność
> > liczenia każdej z różnic jest rzędu n
> > czy też pedantyczniej n*log(n)).

Gdy brać pod uwagę liczbę cyfr, to jest
o wiele gorzej niż napisałem (ale mniejsza :-)

> > Czy można podać istotnie wydajniejszy
> > algorytm, powiedzmy wielomianowy?
> 
> Twoje zadanie po prostym przekształceniu
> staję się pewną szczególną wersją  
> subset-sum, który jest NP-trudny. Zatem,
> bez wykorzystania jakichś sprytnych własności
> ciągu liczb pierwszych, nie spodziewałbym się  
> znalezienia efektywnej metody dla tego problemu
> (a naprawdę nie widzę jak by można było z tych
> własności skorzystać).

Mimo to uważam (a nawet również dlatego), że
optymizacja teg algorytmu jest ciekawym problemem
dla entuzjastów i studentów.

> Dużo prościej byłoby pomyśleć  
> o znalezieniu rozwiązania przybliżonego :-)

I to jest ważniejszy problem (na obecnym
etapie lub w ogóle). Byle podawać ścisłe
ograniczenia z dołu i z góry.

> Przy okazji, na razie szukamy algorytmu
> _wykładniczego_, a nie _wielomianowego_.
> Naiwna metoda jest wykładnicza ze względu na n,
> ale podwójnie wykładnicza ze względu na wielkość
> danych wejściowych (czyli naiwny algorytm jest
> podwójnie wykładniczy).

Więc poproszę podwójnie naiwnie: mógłbyś
poda definicję i napisać kilka słów ekstra
o "podwójnie wykładniczych" algorytmach.

Wspomnę, że Greg Kuperberg przed laty podkreślał
ważność algorytmów które są o wiele gorsze od
wykładniczych. Z pokazji kombinatoryki, i nie
tylko, natykałem sie wciąż na nie. Prowadzi do
nich teoria gier.

Poza tym jednak nie rozumiem jak algorytm,
który jest wukładniczy względem n może być
gorszy niż wykładniczy względem inputu
większego od n - przecież złożoność algorytmu
liczona wzgledem różnych parametrów (ten sam
algorytm, ale złożonośc liczymy na różne sposoby),
jest malejąca względem parametru.

Oświeć mnie, proszę.

Dziękuję, pozdrawiam,

    Włodek


-- 
Wysłano z serwisu Usenet w portalu Gazeta.pl -> http://www.gazeta.pl/usenet/