本網訊（通訊員申國桢）2021年11月30日下午，武漢理工大學理學院數學系彭甯甯副教授在振華樓B214報告廳為我院師生帶來了一場題為“AND-OR樹的最優算法與特征分布”的精彩報告。報告由beat365体育官网邏輯學教研室申國桢副研究員主持。來自beat365体育官网、數學與統計學院、武漢理工大學理學院數學系的10餘位同學參加了此次講座。

彭老師從布爾函數的定義出發，引入了博弈樹的概念，并通過一些實例展示了幾個經典的博弈樹，尤其是T_2^k。接下來，彭老師引入了決定複雜性和随機複雜性，并通過Saks–Widerson定理揭示了這兩種複雜性之間的關系。

接着，彭老師介紹了如何計算一個布爾函數f的随機複雜性R(f)。他首先介紹了分配複雜性P(f)的概念，以及著名的姚期智原則“R(f)=P(f)”，進而把随機複雜性的計算與分配複雜性的計算緊密地聯系在一起。

最後，彭老師介紹了他和導師Tanaka等人在這個領域的研究工作。

在互動環節中，申國桢老師和彭老師就講座中涉及到的一處技術細節問題進行了探讨。數學與統計學院應用數學專業的一位本科生與彭甯甯老師讨論了一些關于博弈樹的問題。

整個講座學術氛圍濃厚，同學們均表示此次報告内容充實、思路清晰、收獲頗豐。

（編輯：鄧莉萍   審稿:嚴璨、吳昕炜）