Logical Subdivisions of NP
Source of Funding: British-German Academic Research
Collaboration (ARC) Programme
The project investigated, amongst other things, positive versions of the complexity class P and showed that these positive versions of P all result in the same class of monotone problems, posP. Complete problems for posP via weak logical reductions were exhibited. Also, a problem posed by Grigni and Sipser in 1992 was resolved by introducing and developing the notion of a positive deterministic Turing machine.