Institute of Information Science, Academia Sinica

Events

Print

Press Ctrl+P to print from browser

Seminar

Applied Logics Seminar Series(XXXVIII) -- Asser's conjecture and descriptive complexity theory

  • LecturerProf. Tony Tan (Department of Computer Science and Information Engineering, National Taiwan University)
    Host: Churn-Jung Liau
  • Time2018-03-23 (Fri.) 15:30 – 17:30
  • LocationAuditorium 108 at IIS Old Building
Abstract

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.