Skip to main content

Institute seminar:

Information

Mondays, o godz. 12:00
Place of the seminar: ICS PAS seminar room
5 Jana Kazimierza Str
e-mail: seminarium@ipipan.waw.pl

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.


© 2021 INSTITUTE OF COMPUTER SCIENCE POLISH ACADEMY OF SCIENCES | Privacy policy | Accessibility declaration