Logo
Unionpedia
Communicatie
Ontdek het op Google Play
Nieuw! Download Unionpedia op je Android™ toestel!
Installeren
Snellere toegang dan browser!
 

NP-volledig

Index NP-volledig

NP-volledigheid is een concept uit de complexiteitstheorie.

17 relaties: Complexiteitsgraad, Computationele complexiteitstheorie, Grafentheorie, Handelsreizigersprobleem, Informatica, Model (wetenschap), NP (complexiteitsklasse), NP-moeilijk, Polynomiale tijd, Polynoom, Stephen Cook, Turingmachine, Vervulbaarheidsprobleem, Verzameling (wiskunde), Wiskunde, Wiskundige, 1970-1979.

Complexiteitsgraad

De complexiteitsgraad van een bepaald algoritme is de manier waarop dat algoritme zich gedraagt als de grootte van het op te lossen probleem toeneemt.

Nieuw!!: NP-volledig en Complexiteitsgraad · Bekijk meer »

Computationele complexiteitstheorie

Computationele complexiteitstheorie is een tak van theoretische informatica en wiskunde die als doel heeft computationele problemen te classificeren in een aantal categorieën die de inherente moeilijkheidsgraad van deze problemen aangeven.

Nieuw!!: NP-volledig en Computationele complexiteitstheorie · Bekijk meer »

Grafentheorie

Enkelvoudige graaf met zes knopen De grafentheorie is een deelgebied van de wiskunde dat de eigenschappen van grafen bestudeert.

Nieuw!!: NP-volledig en Grafentheorie · Bekijk meer »

Handelsreizigersprobleem

Kortste route die de 15 grootste steden van Duitsland aandoet Het handelsreizigersprobleem is een van de bekendste problemen in de informatica en het operationele onderzoek.

Nieuw!!: NP-volledig en Handelsreizigersprobleem · Bekijk meer »

Informatica

Informatica richt zich op de theoretische grondslagen van informatie, de mechanische (automatische) verzameling en verwerking ervan, evenals de praktische toepassingen die eruit voortvloeien.

Nieuw!!: NP-volledig en Informatica · Bekijk meer »

Model (wetenschap)

Een model is een schematische weergave van de werkelijkheid.

Nieuw!!: NP-volledig en Model (wetenschap) · Bekijk meer »

NP (complexiteitsklasse)

Overzicht van P, NP en NP-volledig, mits P ongelijk is aan NP. NP, de aanduiding voor niet-deterministisch polynomiaal, is een complexiteitsklasse die alle beslissingsproblemen bevat die oplosbaar zijn in polynomiale tijd door een niet-deterministische turingmachine.

Nieuw!!: NP-volledig en NP (complexiteitsklasse) · Bekijk meer »

NP-moeilijk

NP-moeilijk is een complexiteitsgraad.

Nieuw!!: NP-volledig en NP-moeilijk · Bekijk meer »

Polynomiale tijd

In de complexiteitstheorie kan een algoritme in polynomiale tijd uitgevoerd worden als de benodigde tijd, als functie van de grootte van de invoer, begrensd wordt door een polynoom.

Nieuw!!: NP-volledig en Polynomiale tijd · Bekijk meer »

Polynoom

Grafiek van de polynoom y.

Nieuw!!: NP-volledig en Polynoom · Bekijk meer »

Stephen Cook

Stephen Andrew Cook (Buffalo, 14 december 1939) is een Amerikaans theoretisch informaticus en hoogleraar aan de Universiteit van Toronto.

Nieuw!!: NP-volledig en Stephen Cook · Bekijk meer »

Turingmachine

In de informatica is de turingmachine een model van berekening en berekenbaarheid, ontwikkeld door de wiskundige Alan M. Turing in zijn beroemde artikel On computable numbers, with an application to the Entscheidungsproblem uit 1936-37.

Nieuw!!: NP-volledig en Turingmachine · Bekijk meer »

Vervulbaarheidsprobleem

In de complexiteitstheorie verwijst het vervulbaarheidsprobleem (ook bekend als SAT, van het Engelse satisfiability) naar het bepalen of een logische propositie vervuld kan worden; een propositie kan vervuld worden als er een toekenning van waar of onwaar aan de atomaire formules bestaat zodanig dat de gehele propositie waar is.

Nieuw!!: NP-volledig en Vervulbaarheidsprobleem · Bekijk meer »

Verzameling (wiskunde)

Venndiagram van de doorsnede A\cap B van twee verzamelingen A en B In de wiskunde is een verzameling een abstract object dat het totaal voorstelt van verschillende objecten, die elementen van de verzameling genoemd worden.

Nieuw!!: NP-volledig en Verzameling (wiskunde) · Bekijk meer »

Wiskunde

Wiskunde (minder gebruikelijk: mathematiek, mathematica of mathesis) is een formele wetenschap die onder andere getallen, patronen en abstracte structuren bestudeert.

Nieuw!!: NP-volledig en Wiskunde · Bekijk meer »

Wiskundige

''Simon Stevin mathematicus insigni'', beroemde wiskundige anonieme Nederlandse graveur, 17e eeuw. Icones Leidenses 40, Universiteit Leiden. Een wiskundige, ook mathemaat of mathematicus, is een geleerde die de wiskunde beoefent.

Nieuw!!: NP-volledig en Wiskundige · Bekijk meer »

1970-1979

1970-1979 De jaren 1970-1979 (van de christelijke jaartelling) zijn een decennium in de 20e eeuw.

Nieuw!!: NP-volledig en 1970-1979 · Bekijk meer »

Richt hier:

NP-compleet.

UitgaandeInkomende
Hey! We zijn op Facebook nu! »