En informàtica, existeixen alguns problemes les solucions dels quals encara no s'han trobat, els problemes es divideixen en classes conegudes com Classes de complexitat . En teoria de la complexitat, una classe de complexitat és un conjunt de problemes amb complexitat relacionada. Aquestes classes ajuden els científics a agrupar problemes en funció del temps i espai que necessiten per resoldre problemes i verificar les solucions. És la branca de la teoria de la computació que tracta dels recursos necessaris per resoldre un problema.

idea intel·ligent vs eclipsi

Els recursos comuns són el temps i l'espai, és a dir, el temps que triga l'algorisme a resoldre un problema i l'ús de memòria corresponent.

• La complexitat temporal d'un algorisme s'utilitza per descriure el nombre de passos necessaris per resoldre un problema, però també es pot utilitzar per descriure quant de temps es necessita per verificar la resposta.
• La complexitat espacial d'un algorisme descriu quanta memòria es necessita perquè l'algorisme funcioni.

Les classes de complexitat són útils per organitzar problemes similars.

Tipus de classes de complexitat

Aquest article tracta les classes de complexitat següents:

1. Classe P
2. Classe NP
3. Classe CoNP
4. NP-dur
5. NP-complet

Classe P

La P a la classe P representa Temps polinomial. És la col·lecció de problemes de decisió (problemes amb una resposta sí o no) que es poden resoldre amb una màquina determinista en temps polinomial.

Característiques:

• La solució a problema P s és fàcil de trobar.
• P Sovint és una classe de problemes computacionals resolubles i tractables. Tractable significa que els problemes es poden resoldre tant en teoria com a la pràctica. Però els problemes que es poden resoldre en teoria però no a la pràctica es coneixen com a insolubles.

Aquesta classe conté molts problemes:

1. Càlcul del màxim comú divisor.
2. Trobar la màxima concordança.
3. Fusionar Ordenar

Classe NP

El NP a la classe NP significa Temps polinomial no determinista . És el conjunt de problemes de decisió que es poden resoldre amb una màquina no determinista en temps polinomial.

Característiques:

• Les solucions de la classe NP són difícils de trobar ja que les resol amb una màquina no determinista, però les solucions són fàcils de verificar.
• Els problemes de NP es poden verificar amb una màquina de Turing en temps polinomial.

Exemple:

Considerem un exemple per entendre millor el Classe NP . Suposem que hi ha una empresa amb un total de 1000 empleats amb un empleat únic identificacions . Suposem que n'hi ha 200 habitacions disponibles per a ells. Una selecció de 200 els empleats han d'estar emparellats, però el director general de l'empresa té les dades d'alguns empleats que no poden treballar a la mateixa habitació per motius personals.
Aquest és un exemple d'un PER EXEMPLE problema. Ja que és fàcil comprovar si l'elecció donada 200 Els empleats proposats per un company de feina són satisfactoris o no, és a dir, cap parella extreta de la llista de companys de feina no apareix a la llista donada pel CEO. Però generar aquesta llista des de zero sembla ser tan difícil que resulta completament impracticable.

aplicacions de computació en núvol

Indica que si algú ens pot donar la solució al problema, podem trobar la parella correcta i incorrecta en temps polinomial. Així per al PER EXEMPLE problema de classe, la resposta és possible, que es pot calcular en temps polinomial.

Aquesta classe conté molts problemes que un voldria poder resoldre de manera eficaç:

1. Problema de satisfacció booleà (SAT).
2. Problema de la trajectòria hamiltoniana.
3. Coloració de gràfics.

Classe Co-NP

Co-NP significa el complement de la classe NP. Vol dir que si la resposta a un problema en Co-NP és No, llavors hi ha una prova que es pot comprovar en temps polinomial.

Característiques:

• Si un problema X està en NP, aleshores el seu complement X’ també està en CoNP.
• Per a un problema NP i CoNP, no cal verificar totes les respostes alhora en temps polinomial, cal verificar només una resposta particular sí o no en temps polinomial perquè un problema estigui en NP o CoNP.

Alguns exemples de problemes per a CoNP són:

1. Per comprovar el nombre primer.
2. Factorització de nombres enters.

NP-classe difícil

Un problema NP-difícil és almenys tan difícil com el problema més difícil de NP i és una classe de problemes de tal manera que cada problema de NP es redueix a NP-difícil.

Característiques:

• Tots els problemes NP-hard no estan a NP.
• Es necessita molt de temps per comprovar-los. Això vol dir que si es dóna una solució per a un problema NP-difícil, es necessita molt de temps per comprovar si és correcte o no.
• Un problema A està en NP-difícil si, per a cada problema L en NP, hi ha una reducció de temps polinomial de L a A.

Alguns dels exemples de problemes a Np-hard són:

1. Problema d'aturada.
2. Fórmules booleanes qualificades.
3. No hi ha cicle hamiltonià.

Classe NP-completa

Un problema és NP-complet si és alhora NP i NP-dur. Els problemes NP-complets són els problemes difícils de NP.

què és una pila en java

Característiques:

• Els problemes NP-complets són especials, ja que qualsevol problema de la classe NP es pot transformar o reduir en problemes NP-complets en temps polinomial.
• Si es pogués resoldre un problema NP-complet en temps polinomial, també es podria resoldre qualsevol problema NP en temps polinomial.

Alguns exemples de problemes inclouen:

1. Cicle Hamiltonià.
2. Satisfacció.
3. Coberta de vèrtex .