15.04.2024 - Seminarium Instytutowe — godz. 12:00
Michał Makowski (Wydział Matematyki, Informatyki i Mechaniki Uniwersytetu Warszawskiego)
Streszczenie (autorskie):
Warunkowa niezależność zmiennych losowych X i Y pod warunkiem Z intuicyjnie oznacza, że znając Z, jakakolwiek wiedza o X nie mówi nam nic o Y i vice versa. Naturalnie pojawia się chęć wnioskowania o zależnościach pomiędzy tymi niezależnościami. Jak się okazuje, nie istnieje skończony system aksjomatów charakteryzujący warunkową niezależność zmiennych losowych. Co więcej, problem decyzyjny pytający, czy zachodzi implikacja pomiędzy daną koniunkcją warunkowych niezależności a inną daną warunkową niezależnością, jest nierozstrzygalny. Wykazał to w 2022 Cheuk Ting Li oraz niezależnie Kühne i Yashfe. Można rozważać wariant problemu, w którym dziedziny zmiennych są ograniczone, np. do zbioru dwuelementowego. Nietrudno pokazać, że wariant ten należy do klasy złożoności EXPSPACE. W pracy magisterskiej budującej na publikacji C. T. Li wykazałem co-NEXPTIME-trudność tego wariantu problemu. W wystąpieniu przedstawię elementy wykorzystanej konstrukcji, która pozwala za pomocą wyrażeń warunkowej niezależności modelować problem kafelkowania, a co za tym idzie dowolną maszynę Turinga.