18 April 2025, 10:30-11:30.
ENS, room S16/FS101 (Aile Rataud, level -1).
Ontoplex: An Ontology of Computational Complexity
Everyone heard of P, NP, and the related one-million-dollars question. Database theorists are also used to “parallel computation classes”, such as AC, NC, and TC. Cryptographists love their BPP and BQP. But did you know there was also a class called HVPZK?
There are just so many known complexity classes and connections between them, scattered across thousands of papers… It is time to put them all in one database.
I will discuss an ongoing effort of creating a knowledge graph of computational complexity, with query answering and automated reasoning.
