Problemy ze złożonością między P i NP, które mają uogólnienia NP-zupełne

13

Czy ktoś może wymienić niektóre dobrze znane problemy, które spełniają następujące warunki:

1. has a generalization problem that is known to be NP-complete
2. has not been proved to be NP-complete nor has a known polynomial time solution. 
sma
źródło
5
co masz na myśli przez problem generacji?
Shiva Kintali,
Przepraszam, miałem na myśli uogólnienie.
sma

Odpowiedzi:

18

Najsłynniejsze: wykres izomorfizmu i dominacja w turniejach.

Uogólnienia są naturalne.

Yixin Cao
źródło
10
W szczególności jednym uogólnieniem GI jest izomorfizm subgraficzny, którym jest NPC
Suresh Venkat
14

Kolejny naturalny: znalezienie równowagi Nasha nie jest (prawdopodobnie) NPC, ale znalezienie takiej z pewną naturalną właściwością (np. Która maksymalizuje sumę narzędzi gracza) to NPC. Oryginalny dowód NPC został napisany przez Gilboa i Zemela pod koniec lat 80., a najnowsze odniesienia można znaleźć np. Http://www.cs.duke.edu/~conitzer/nashGEB08.pdf

Noam
źródło
4

KJMK={AiM}MXKJ={AiBi}XJAiBiJAiXBiX

JK

Michaił Babin
źródło