Seminarium KMMF "Teoria Dwoistości"

W trakcie spotkania (częściowo po polsku a częściowo po angielsku) będędyskutować dwa tematy:1. Warszawska matematyka lat 70ych. Ta część spotkania poświęcona będzieprzede wszystkim p. prof. Mostowskiemu(którego stulecie właśnie obchodzimy), ogólnym wspomnieniom dotyczacych matematyki warszawskiej z pewnymi elementami stosunków z "fizykami matematycznymi". Uwagi moje będą prawdopodobnie niezbyt koherentne.2. Propositional Satisfiability (SAT). Jest to ogólny mechanizm rozwiązywania "finite-domain Constraint Satisfaction Problems". Kiedy problemy reprezentowane są jako tzw. CNF, problemy losowe w ktorych klauzule (wszystko będzie wytlumaczone w trakcie referatu) sa zadanej dlugosci >= 3 maja wlasnosc "zmiany stanu" (ang. "Phase transition"). Własność ta była badana przez fizyków (włączając w to R. Zecchina'e i kolegów), ale dowód istnienia owej zmiany stanu przypisywany jest D. Achiloptas'owi. Intuicje fizyczne związane ze zmiana stanu okazały się ważne w badaniach SAT. Omówię podstawowe własności SAT i wspomnęWalkSAT, solver (program rozwiązujący?) dla SAT oparty o "random walk". Wspomnę tez najrozmaitsze problemy gdzie (jak myślę) techniki "ciągłe" mogą mięć w SAT zastosowania.