Gegeven zijn de beslissingsproblemen A, B en C met A ≤ B en B ≤ C. Het is bekend dat B een NPC probleem is. Dan geldt in ieder geval, dat:
  1. als C een NP-probleem is, dan is A een P-probleem
  2. als B ≤ A, dan is A ook een NPC-probleem.
  3. C een NP-hard probleem is.
  4. A een NP-probleem is.

  • Antwoord 2,3 en 4 zijn goed.

    Omdat NP naar beneden gesloten is onder ≤, geldt A ∈ NP. C is een NP­hard probleem, omdat B een NPC probleem
    is en B ≤ C.
    Als B ≤ A, dan zijn A en B even moeilijk en omdat A een NP probleem is, is A nu een NPC probleem.
    Als C een NP probleem is, dan is C een NPC probleem en A een NP probleem. Hieruit is niet af te leiden dat A een P
    probleem is.

    Rapporteer Plaats commentaar
    0
Startpagina / Flashcards / gegeven-zijn-de-beslissingsproblemen-b-en-c-met-b-en-b-c-het-is-bekend-dat-b-een-npc-probleem-is-dan-geldt-in-ieder-geval-dat-als-c-een-np-probleem-is-dan-is-een-p-probleemals-b-dan-is-ook-een-npc