Witam!
Drobne wprowadzenie, o maszynie Turinga. Otóż jest to model hipotetycznego komputera, składającego się z taśmy o nieskończonej długości podzielonej na pola, oraz z głowicy. Pole może mieć jeden z n stanów, a głowica jeden z m stanów. Głowica po otrzymaniu polecenia od programu sterującego może zmienić wartość pola nad którym się znajduje, zmienić swój stan a następnie przesunąć się w lewo, w prawo lub zakończyć pracę. Takie urządzenie służy do wykonywania algorytmów. Dla zainteresowanych odsyłam do szczegółowego artykułu na Wikipedii: http://pl.wikipedia.org/wiki/Maszyna_Turinga (przepraszam tych, którzy już wiedzą, o czym mowa).
Z tego, co dowiedziałem się na wykładzie wynika, że niedeterministyczna maszyna Turinga może składać się z N taśm, a dla danej pary pole-stan może istnieć więcej niż jedna instrukcja. Zatem problemy o złożoności obliczeniowej i czasowej klasy NP można by przesunąć do klasy P.
Generowanie (a w zasadzie sprawdzanie, czy zadana liczba jest liczbą pierwszą) jest problemem o złożoności obliczeniowej O(n^2) (o ile dobrze pamiętam, jeśli się mylę, przepraszam za błąd). Czy zatem budowa fizycznej niedeterministycznej maszyny Turinga pozwoliłaby na odkrycie algorytmu generowania liczb pierwszych, o wielomianowej złożoności? Czy spowodowałoby to upublicznienie wszystkich tajnych danych, skoro podstawa współczesnej kryptografii stoi właśnie na liczbach pierwszych?\
Pozdrawiam!
Drobne wprowadzenie, o maszynie Turinga. Otóż jest to model hipotetycznego komputera, składającego się z taśmy o nieskończonej długości podzielonej na pola, oraz z głowicy. Pole może mieć jeden z n stanów, a głowica jeden z m stanów. Głowica po otrzymaniu polecenia od programu sterującego może zmienić wartość pola nad którym się znajduje, zmienić swój stan a następnie przesunąć się w lewo, w prawo lub zakończyć pracę. Takie urządzenie służy do wykonywania algorytmów. Dla zainteresowanych odsyłam do szczegółowego artykułu na Wikipedii: http://pl.wikipedia.org/wiki/Maszyna_Turinga (przepraszam tych, którzy już wiedzą, o czym mowa).
Z tego, co dowiedziałem się na wykładzie wynika, że niedeterministyczna maszyna Turinga może składać się z N taśm, a dla danej pary pole-stan może istnieć więcej niż jedna instrukcja. Zatem problemy o złożoności obliczeniowej i czasowej klasy NP można by przesunąć do klasy P.
Generowanie (a w zasadzie sprawdzanie, czy zadana liczba jest liczbą pierwszą) jest problemem o złożoności obliczeniowej O(n^2) (o ile dobrze pamiętam, jeśli się mylę, przepraszam za błąd). Czy zatem budowa fizycznej niedeterministycznej maszyny Turinga pozwoliłaby na odkrycie algorytmu generowania liczb pierwszych, o wielomianowej złożoności? Czy spowodowałoby to upublicznienie wszystkich tajnych danych, skoro podstawa współczesnej kryptografii stoi właśnie na liczbach pierwszych?\
Pozdrawiam!