University of Leicester

informatics

Logical Subdivisions of NP

Source of Funding: British-German Academic Research Collaboration (ARC) Programme
Amount: 3,550
Duration: September 1994 - August 1997
Principal Investigators: Prof. Dr. Clemens Lautemann (University of Mainz, Germany), Prof. Iain Stewart
Other Investigators: Dr. Juha Nurmonen, Dr. Thomas Schwentick (University of Mainz, Germany), Mr. Richard Gault

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.

University of Leicester 15th December 2000. Last modified: 8th January 2004, 14:33:02.
Informatics Web Maintainer. This document has been approved by the Head of Department.