DOI: 10.5176/978-981-08-7240-3_I-19
Authors: Soha Safwat, Wafik Lotfalah and Ibrahim Farag
Abstract:
Descriptive complexity emerged from finite model theory and had its aims in finding logics that capture computational complexity classes. Observing that imperative programming languages can also be considered as logics (maybe with some additional control), we extend the scope of descriptive complexity by defining two fragments of such languages and showing that they capture the classes P and NP.
Updating...