Springen naar inhoud

Vulbaarheidsprobleem


  • Log in om te kunnen reageren

#1

Der Dafmeister

    Der Dafmeister


  • >25 berichten
  • 37 berichten
  • Gebruiker

Geplaatst op 03 mei 2010 - 15:50

Op wikipedia las ik een artikeltje over de conjunctieve normaalvorm (CNF). Hierin stond dat binnen de complexiteitstheorie het vulbaarheidsprobleem bestaat waarbij wordt onderzocht of een formule in de conjunctieve normaal vorm vervulbaar is. Dit vulbaarheidsprobleem (ook wel bekend als CNF-SAT) is een NP-compleet probleem.

In het artikel van de disjunctieve normaalvorm (DNF) staat dat het vulbaarheidsprobleem binnen polynominale tijd kan worden opgelost.

Nu is mijn vraag, waarom wordt voor het oplossen van dit vraagstuk niet altijd de formule geconverteerd van CNF naar DNF? Is dit onmogelijk of kan dit niet in polynominale tijd?

Dit forum kan gratis blijven vanwege banners als deze. Door te registeren zal de onderstaande banner overigens verdwijnen.

#2

Sjoerdl

    Sjoerdl


  • 0 - 25 berichten
  • 1 berichten
  • Gebruiker

Geplaatst op 05 mei 2010 - 20:20

Neem eens een voorbeeld in CNF en probeer dat te vertalen naar DNF.
LaTeX
(volgens mij heb ik ze nu allemaal...)

Zoals je nu waarschijnlijk al ziet, groeit het aantal formules dat je moet opstellen in DNF enorm als je wat grotere formules krijgt in CNF. Ofwel: de omzetting lukt niet in polynomiale tijd. Als je wel een omzetting weet te vinden die in polynomiale tijd draait, heb je ook meteen P=NP opgelost :-)





0 gebruiker(s) lezen dit onderwerp

0 leden, 0 bezoekers, 0 anonieme gebruikers

Ook adverteren op onze website? Lees hier meer!

Gesponsorde vacatures

Vacatures