In informatica esistono alcuni problemi le cui soluzioni non sono ancora state trovate, i problemi sono divisi in classi dette Classi di complessità . Nella teoria della complessità, una classe di complessità è un insieme di problemi con relativa complessità. Queste classi aiutano gli scienziati a raggruppare i problemi in base al tempo e allo spazio necessari per risolverli e verificare le soluzioni. È la branca della teoria della computazione che si occupa delle risorse necessarie per risolvere un problema.

chiave composita a chiave primaria

Le risorse comuni sono tempo e spazio, ovvero quanto tempo impiega l'algoritmo per risolvere un problema e il corrispondente utilizzo della memoria.

• La complessità temporale di un algoritmo viene utilizzata per descrivere il numero di passaggi necessari per risolvere un problema, ma può anche essere utilizzata per descrivere quanto tempo occorre per verificare la risposta.
• La complessità spaziale di un algoritmo descrive la quantità di memoria necessaria affinché l'algoritmo funzioni.

Le classi di complessità sono utili per organizzare tipi simili di problemi.

Tipi di classi di complessità

In questo articolo vengono trattate le seguenti classi di complessità:

1. Classe P
2. Classe NP
3. Classe CoNP
4. NP-difficile
5. NP-completo

Classe P

La P nella classe P sta per Tempo polinomiale. È l'insieme dei problemi decisionali (problemi con risposta sì o no) che possono essere risolti da una macchina deterministica in tempo polinomiale.

Caratteristiche:

• La soluzione a problema P s è facile da trovare.
• P è spesso una classe di problemi computazionali che sono risolvibili e trattabili. Trattabile significa che i problemi possono essere risolti sia in teoria che in pratica. Ma i problemi che possono essere risolti in teoria ma non in pratica sono detti intrattabili.

Questa classe contiene molti problemi:

1. Calcolo del massimo comun divisore.
2. Trovare un abbinamento massimo.
3. Unisci ordinamento

Classe NP

L'NP nella classe NP sta per Tempo polinomiale non deterministico . È l'insieme dei problemi decisionali che possono essere risolti da una macchina non deterministica in tempo polinomiale.

Caratteristiche:

• Le soluzioni della classe NP sono difficili da trovare poiché vengono risolte da una macchina non deterministica ma sono facili da verificare.
• I problemi di NP possono essere verificati da una macchina di Turing in tempo polinomiale.

Esempio:

Consideriamo un esempio per comprendere meglio il Classe NP . Supponiamo che ci sia un'azienda con un totale di 1000 dipendenti che hanno un dipendente unico ID . Supponiamo che ci siano 200 camere a loro disposizione. Una selezione di 200 i dipendenti devono essere accoppiati, ma l’amministratore delegato dell’azienda dispone dei dati di alcuni dipendenti che non possono lavorare nella stessa stanza per motivi personali.
Questo è un esempio di un PER ESEMPIO problema. Poiché è facile verificare se la scelta data è 200 dipendenti proposti da un collega sono soddisfacenti o meno, ovvero nessuna coppia presa dall'elenco dei colleghi appare nell'elenco fornito dall'amministratore delegato. Ma generare un elenco del genere da zero sembra essere così difficile da risultare del tutto impraticabile.

Katrina Kaif

Indica che se qualcuno può fornirci la soluzione al problema, possiamo trovare la coppia corretta e quella errata in tempo polinomiale. Quindi per il PER ESEMPIO problema di classe, la risposta è possibile, che può essere calcolata in tempo polinomiale.

Questa classe contiene molti problemi che si vorrebbe essere in grado di risolvere in modo efficace:

1. Problema di soddisfacibilità booleano (SAT).
2. Problema del cammino hamiltoniano.
3. Colorazione del grafico.

Classe Co-NP

Co-NP sta per il complemento della Classe NP. Ciò significa che se la risposta a un problema in Co-NP è No, allora esiste una prova che può essere verificata in tempo polinomiale.

Caratteristiche:

• Se un problema X è in NP, allora anche il suo complemento X’ è in CoNP.
• Per un problema NP e CoNP, non è necessario verificare tutte le risposte contemporaneamente in tempo polinomiale, è necessario verificare solo una particolare risposta sì o no in tempo polinomiale affinché un problema sia in NP o CoNP.

Alcuni esempi di problemi per CoNP sono:

1. Per controllare i numeri primi.
2. Fattorizzazione di numeri interi.

Classe NP-difficile

Un problema NP-difficile è difficile almeno quanto il problema più difficile in NP ed è una classe di problemi tale che ogni problema in NP si riduce a NP-difficile.

Caratteristiche:

• Tutti i problemi NP-difficili non sono in NP.
• Ci vuole molto tempo per controllarli. Ciò significa che se viene fornita una soluzione per un problema NP-difficile, ci vorrà molto tempo per verificare se sia corretta o meno.
• Un problema A è in NP-difficile se, per ogni problema L in NP, esiste una riduzione in tempo polinomiale da L ad A.

Alcuni esempi di problemi in Np-hard sono:

1. Problema di arresto.
2. Formule booleane qualificate.
3. Nessun ciclo hamiltoniano.

Classe NP-completa

Un problema è NP-completo se è sia NP che NP-difficile. I problemi NP-completi sono i problemi difficili in NP.

restituendo array in Java

Caratteristiche:

• I problemi NP-completi sono speciali poiché qualsiasi problema nella classe NP può essere trasformato o ridotto in problemi NP-completi in tempo polinomiale.
• Se si potesse risolvere un problema NP-completo in tempo polinomiale, allora si potrebbe risolvere anche qualsiasi problema NP in tempo polinomiale.

Alcuni problemi di esempio includono:

1. Ciclo Hamiltoniano.
2. Soddisfabilità.
3. Copertura del vertice .