講 題： |
應用邏輯討論會系列 (XXXVIII) - Asser's conjecture and descriptive complexity theory |

講 者： |
陳偉松 教授 (國立臺灣大學資訊工程學系) |

時 間： |
2018-03-23 (Fri) 15:30 – 17:30 |

地 點： |
資訊所舊館108演講廳 |

邀請人： |
廖純中 |

**摘要:**
In 1951, Scholz defined the notion of first-order spectra, and immediately after, in 1955, Asser asked a seemingly innocent question whether first-order spectra are closed under complement. It was rather surprising that in 1970's Jones, Selman and Fagin showed that Asser's question is indeed equivalent to the question NE vs. co-NE. In this talk we will briefly review the connection between Asser's conjecture and descriptive complexity theory. We will also highlight some recent results.