Problem spełnialności formuł rachunku zdań SAT jest jednym z fundamentalnych oraz otwartych zadań we współczesnej informatyce. Jest on problemem
N P-zupełnym. To znaczy, że wszystkie problemy z klasy NP możemy sprowadzić do
problemu SAT w czasie wielomianowym. Co ciekawe, wśród problemów z klasy NP
istnieje wiele takich, które są ściśle związanych z kryptologią, na przykład: faktoryzacja liczb – ważna dla RSA, łamanie kluczy szyfrów symetrycznych, znajdowanie kolizji
funkcji skrótu i wiele innych. Odkrycie wielomianowego algorytmu dla SAT skutkowa-
łoby rozwiązaniem problemu milenijnego: P vs. NP. Cel ten wydaje się bardzo trudny
do osiągnięcia – nie wiadomo nawet czy jest możliwy. Mając nieco mniejsze aspiracje
możemy projektować algorytmy heurystyczne lub losowe dla SAT. W związku z tym,
głównym celem autorów pracy jest przedstawienie projektu równoległego SAT Solvera
bazującego na algorytmie WalkSAT, w tym procesu jego implementacji z wykorzystaniem środowiska programistycznego OpenCL oraz komputera wyposażonego w karty
graficzne NVIDIA Tesla. Wraz z dynamicznym rozwojem technologii procesorów typu
GPU oraz układów FPGA, jak również przenośnością rozwiązań stworzonych w OpenCL,
kierunek takich prac staje się interesujący ze względu na uzyskiwaną efektywność obliczeniową, jak również szybkość prototypowania rozwiązań.
REFERENCJE(30)
1.
T. Eibach, E. Pilz, and G. Volkel ¨ , Attacking Bivium Using SAT Solvers, University of Ulm, Institute of Theoretical Computer Science http://www.uni-ulm.de/fileadmi... uni ulm/iui.inst.190 /Mitarbeiter/eibach/Attacking-Bivium-Using-SAT-Solvers.pdf, 01.02.2014.
S. Anthony, 7nm, 5nm, 3nm: The new materials and transistors that will take us to the limits of Moores law, http://www.extremetech.com/com...- -new-materials-and-transistors-that-will-take-us-to-the-limits-of-moores-law, 24.04.2014.
C. F. Madigan, S. Malik, M. W. Moskewicz, L. Zhang, Y. Zhao, Chaff: Engineering an Efficient SAT Solver, 39th Design Automation Conference (DAC 2001), ACM, 2001.
H. H. Hoos, D. A. D. Tompkins, Novelty+ and Adaptive Novelty+, https://cs.uwaterloo.ca/ dtompkin/papers/satcomp04-novp.pdf, University of British Columbia, 2004.
G. V. Bard, Algorithms for Solving Linear and Polynomial Systems of Equations over Finite Fields with Applications to Cryptanalysis, Rozprawa doktorska, 2007.
Przetwarzamy dane osobowe zbierane podczas odwiedzania serwisu. Realizacja funkcji pozyskiwania informacji o użytkownikach i ich zachowaniu odbywa się poprzez dobrowolnie wprowadzone w formularzach informacje oraz zapisywanie w urządzeniach końcowych plików cookies (tzw. ciasteczka). Dane, w tym pliki cookies, wykorzystywane są w celu realizacji usług, zapewnienia wygodnego korzystania ze strony oraz w celu monitorowania ruchu zgodnie z Polityką prywatności. Dane są także zbierane i przetwarzane przez narzędzie Google Analytics (więcej).
Możesz zmienić ustawienia cookies w swojej przeglądarce. Ograniczenie stosowania plików cookies w konfiguracji przeglądarki może wpłynąć na niektóre funkcjonalności dostępne na stronie.