Wykład mgr inż. Marka Malinowskiego "W kręgach spełnialności..."
Tytułowa tematyka i inne pokrewne problemy były przedmiotem kilkuletnich prac autora wykładu. Niektóre rezultaty tych badań były już wcześniej prezentowane (np. prezentacja Złamanie niedetrminizmu problemów NP-zupełnych w ramach IV seminarium Centrum Informatyzacji i Centrum Studiów Zaawansowanych Politechniki Warszawskiej oraz prezentacja Efektywność w algorytmice). Dzisiaj, gdy uzyskane wyniki przyjęły dojrzały kształt, warte są przedstawienia i przedyskutowania.
Rolę zachęty do udziału w takiej dyskusji i zaproszenia na wykład niech spełni fragment przedmowy do przygotowanej do druku książki „P versus NP – nowa perspektywa”.
[ … Prezentowane wyniki powinny być zrozumiałe i czytelne. Liczę więc, że znajdą zainteresowanie. Wyrażone oczekiwania wynikają z kilku przesłanek.
Po pierwsze, uważam podobnie jak Ralph Merkle, że zarówno koncepcje jak i same rozwiązania warte są dalszej pracy i „… nie mogą być błędne tylko dlatego, że są proste”. Otwierając nową perspektywę, mimo destrukcyjnego charakteru, „ … jest oczywiste, że powinny być udostępnione”.
Po drugie, jeden z dyskutowanych w książce problemów autoryzowali Panowie Adleman, Rivest i Shamir. Zakładam więc, że każdy, dla którego tematyka książki nie jest obca, ma świadomość znaczenia rozwiązania tego i pozostałych dyskutowanych problemów. Pisze o tym Pan Schneier w swojej książce „Cryptography”. Także Panowie Arora i Barak piszą o tym w przeglądanym przeze mnie drafcie ich książki „Computational Complexity: A Modern Approach”.
Po trzecie, moje rozwiązania wykorzystują z jednej strony znane już podstawowe wyniki badań w teorii złożoności. Z drugiej strony wykorzystują zupełnie nowe pomysły odwzorowane przez elementarne modele. … ]
Warta rozwinięcia jest trzecia przesłanka wspomnianych oczekiwań autora wykładu. Składające się na prezentację rozwiązania tytułowych problemów, do ich rozumienia i ich oceny nie wymagają zaawansowanego aparatu matematycznego i wyrafinowanych formalizmów. W odniesieniu do SPEŁNIALNOŚCI (SATISFABILITY, w skrócie SAT) wystarcza elementarna wiedza z logiki matematycznej, a elementy geometrii analitycznej na płaszczyźnie do rozumienia rozwiązania FAKTORYZACJI (FACTORING).