Arbeitsgruppe Theoretische Informatik

NP-intermediate

Ansprechpartner: Fabian Müller

Eine der wichtigsten offenen Fragen in der Theoretischen Informatik ist, ob P = NP gilt. Wir betrachten in diesem Kontext eine Menge von Problemen, die man als NP-intermediate bezeichnet. Dabei handelt es sich um Probleme, für die man bisher nur zeigen konnte, dass sie in NP liegen, aber nicht NP-vollständig sind.

Ziel der Arbeitet ist es, eine Übersicht über besagte Probleme zu schaffen.

Quellen

  1. http://dl.acm.org/citation.cfm?doid=321864.321877
  2. http://gustavnordh.com/blowing_holes_revised.pdf