Stiamo lavorando per ripristinare l'app di Unionpedia nel Google Play Store
UscenteArrivo
🌟Abbiamo semplificato il nostro design per una migliore navigazione!
Instagram Facebook X LinkedIn

NP-completo

Indice NP-completo

Nella teoria della complessità computazionale i problemi NP-completi sono i più difficili problemi nella classe NP ("problemi risolvibili non-deterministicamente in tempo polinomiale") nel senso che, se si trovasse un algoritmo in grado di risolvere "velocemente" (nel senso di utilizzare tempo polinomiale) un qualsiasi problema NP-completo, allora si potrebbe usarlo per risolvere "velocemente" ogni problema in NP.

Indice

  1. 45 relazioni: Algoritmo, Algoritmo di approssimazione, Algoritmo euristico, Algoritmo greedy, Cambridge (Massachusetts), Cammino hamiltoniano, Christos Papadimitriou, Classe di complessità, Classi di complessità P e NP, Co-NP, Colorazione dei grafi, Complemento (complessità), Complessità temporale, David S. Johnson, Garey, Gioco del quindici, Grafo, Insieme, Insieme indipendente (teoria dei grafi), Introduzione agli algoritmi, Isomorfismo, Isomorfismo di sottografi, Istituto matematico Clay, John Hopcroft, Lingua inglese, Macchina di Turing, Marek Karpinski, NP-completo, NP-difficile, Numero intero, Problema del commesso viaggiatore, Problema della cricca, Problema delle somme parziali, Problema dello zaino, Problema di copertura dei vertici, Reduced instruction set computer, Richard Karp, Ronald Rivest, Se e solo se, Soddisfacibilità booleana, Teorema di Cook-Levin, Teoria dei grafi, Teoria della complessità computazionale, Thomas H. Cormen, Università di Liverpool.

  2. Classi di complessità
  3. Ottimizzazione
  4. Problemi NP-completi

Algoritmo

In matematica e informatica un algoritmo è la specificazione di una sequenza finita di operazioni (dette anche istruzioni) che consente di risolvere tutti i quesiti di una stessa classe o di calcolare il risultato di un'espressione matematica.

Vedere NP-completo e Algoritmo

Algoritmo di approssimazione

Nell'informatica e nella ricerca operativa, un algoritmo di approssimazione è un algoritmo usato per trovare soluzioni approssimate a problemi di ottimizzazione.

Vedere NP-completo e Algoritmo di approssimazione

Algoritmo euristico

Algoritmo euristico (o euristica): in matematica e informatica è un particolare tipo di algoritmo progettato per risolvere un problema più velocemente, nel caso in cui i metodi classici siano troppo lenti nel calcolo (ad esempio, in caso di elevata complessità computazionale) o per trovare una soluzione approssimata, nel caso in cui i metodi classici falliscano nel trovare una soluzione esatta.

Vedere NP-completo e Algoritmo euristico

Algoritmo greedy

Un algoritmo greedy è un paradigma algoritmico in base al quale la ricerca di una soluzione ottimale avviene seguendo una strategia euristica di problem-solving in cui l'algoritmo, a ogni passaggio, opta per la soluzione ottimale a livello locale (come definita in precedenza dal programmatore).

Vedere NP-completo e Algoritmo greedy

Cambridge (Massachusetts)

Cambridge è una città degli Stati Uniti d'America, capoluogo insieme a Lowell della contea di Middlesex nello stato del Massachusetts. Fu chiamata così in onore della città universitaria inglese di Cambridge.

Vedere NP-completo e Cambridge (Massachusetts)

Cammino hamiltoniano

Nel campo matematico della teoria dei grafi, un cammino in un grafo (orientato o non orientato) è detto hamiltoniano se esso tocca tutti i vertici del grafo una e una sola volta.

Vedere NP-completo e Cammino hamiltoniano

Christos Papadimitriou

Nel 1972 Papadimitriou ha conseguito la laurea in ingegneria elettrica all'Università tecnica nazionale di Atene. Ha poi continuato i suoi studi all'Università di Princeton, dove ha conseguito prima la laurea magistrale in ingegneria elettrica nel 1974 e poi il dottorato di ricerca in informatica due anni più tardi.

Vedere NP-completo e Christos Papadimitriou

Classe di complessità

Nella teoria della complessità computazionale, una classe di complessità è un insieme di problemi di una certa complessità. Un esempio tipico di definizione di classe di complessità ha la forma: Ad esempio, la classe NP è l'insieme dei problemi di decisione che possono essere risolti da una macchina di Turing non deterministica in tempo polinomiale, mentre la classe P è l'insieme dei problemi di decisione che possono essere risolti da una macchina di Turing deterministica in tempo polinomiale.

Vedere NP-completo e Classe di complessità

Classi di complessità P e NP

Il problema delle classi P e NP è un problema tuttora aperto nella teoria della complessità computazionale. Nonostante ci sia in palio un premio di un milione di dollari il problema rimane ancora senza una soluzione (si tratta di uno dei problemi del millennio).

Vedere NP-completo e Classi di complessità P e NP

Co-NP

Nella teoria della complessità computazionale, coNP è la classe di problemi complementari a quelli della classe NP. In maniera più formale si ha che se S è un problema su un alfabeto A allora esso è un problema della classe coNP se e solo se A^* backslash S.

Vedere NP-completo e Co-NP

Colorazione dei grafi

Nella teoria dei grafi, la colorazione dei grafi è un caso speciale di etichettamento dei grafi; è un'assegnazione di etichette, tradizionalmente chiamate "colori", agli elementi di un grafo soggetta a determinati vincoli.

Vedere NP-completo e Colorazione dei grafi

Complemento (complessità)

Nella teoria della complessità computazionale, il complemento di un problema decisionale è il problema risultante dall'inversione delle risposte sì e no.

Vedere NP-completo e Complemento (complessità)

Complessità temporale

In informatica, la complessità temporale di un algoritmo quantifica la quantità di tempo impiegata da un algoritmo a essere eseguito in funzione della lunghezza della stringa che rappresenta l'input:226.

Vedere NP-completo e Complessità temporale

David S. Johnson

È stato a capo del dipartimento Algorithms and Optimization di AT&T Labs Research dal 1988 al 2013 ed è stato visiting professor alla Columbia University dal 2014 al 2016.

Vedere NP-completo e David S. Johnson

Garey

Garey è un census-designated place (CDP) degli Stati Uniti d'America, situato nello stato della California, nella contea di Santa Barbara.

Vedere NP-completo e Garey

Gioco del quindici

Il gioco del quindici è un rompicapo classico creato nel 1874 da Noyes Palmer Chapman (North Stonington, 14 gennaio 1811 – Canastota, 28 aprile 1889), postino in servizio a Canastota, e popolarizzato nel 1891 da Samuel Loyd.

Vedere NP-completo e Gioco del quindici

Grafo

I grafi sono strutture matematiche discrete che rivestono interesse sia per la matematica che per un'ampia gamma di campi applicativi. In ambito matematico il loro studio, la teoria dei grafi, costituisce un'importante parte della combinatoria; i grafi inoltre sono utilizzati in aree come topologia, teoria degli automi, funzioni speciali, geometria dei poliedri, algebre di Lie.

Vedere NP-completo e Grafo

Insieme

In matematica, una collezione di elementi rappresenta un insieme se esiste un criterio oggettivo che permette di decidere univocamente se un qualunque elemento fa parte o no del raggruppamento.

Vedere NP-completo e Insieme

Insieme indipendente (teoria dei grafi)

Nella teoria dei grafi, un insieme indipendente o insieme stabile è un insieme di vertici in un grafo, nessuno dei quali è adiacente a due a due.

Vedere NP-completo e Insieme indipendente (teoria dei grafi)

Introduzione agli algoritmi

Introduzione agli algoritmi e strutture dati (Introduction to Algorithms) è un libro di Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest e Clifford Stein.

Vedere NP-completo e Introduzione agli algoritmi

Isomorfismo

In matematica, in particolare in algebra astratta, un isomorfismo (dal greco ἴσος, isos, che significa uguale, e μορφή, morphé, che significa forma) è un'applicazione biunivoca fra oggetti matematici tale che l'applicazione e la sua inversa siano omomorfismi.

Vedere NP-completo e Isomorfismo

Isomorfismo di sottografi

Nella teoria della complessità computazionale, l'isomorfismo di sottografo è un problema decisionale di tipo NP-completo. La descrizione del problema è la seguente: siano dati G1 e G2 due grafi, è G1 isomorfo ad un sottografo di G2? La ricerca del sottografo isomorfo ha applicazioni in chemioinformatica.

Vedere NP-completo e Isomorfismo di sottografi

Istituto matematico Clay

L'Istituto matematico Clay (Clay Mathematics Institute o CMI) è una fondazione privata no-profit con sede a Cambridge (Massachusetts, USA) dedicata all'accrescimento ed alla diffusione della conoscenza della matematica.

Vedere NP-completo e Istituto matematico Clay

John Hopcroft

Nell'ambito dell'informatica teorica ha scritto, insieme a Jeffrey D. Ullman e Rajeev Motwani, il libro Introduction to Automata Theory, Languages, and Computation (tradotto in italiano da Giovanni Pighizzini con il titolo Automi, linguaggi e calcolabilità).

Vedere NP-completo e John Hopcroft

Lingua inglese

Linglese (nome nativo: English) è una lingua indoeuropea, parlata da circa 1,452 miliardi di persone al 2022. Secondo Ethnologue 2022 (25ª edizione), è la lingua più parlata al mondo per numero di parlanti totali (nativi e stranieri) ed è la terza per numero di parlanti madrelingua (L1) (la prima è il cinese e la seconda è lo spagnolo).

Vedere NP-completo e Lingua inglese

Macchina di Turing

In informatica, una macchina di Turing (o più brevemente MdT) è una macchina ideale che manipola i dati contenuti su un nastro di lunghezza potenzialmente infinita, secondo un insieme prefissato di regole ben definite.

Vedere NP-completo e Macchina di Turing

Marek Karpinski

Ha lavorato nel campo della ricerca e di insegnamento in varie università europee ed americane, fra l'altro, in Berkeley, Princeton e Bonn. Ha una grande influenza scientifica, soprattutto nei campi di algoritmi di approssimazione per problemi di ottimizzazione NP-hard, la teoria del VC-dimension così come altre tecniche computazionali di limiti inferiori per diversi modelli computazionali.

Vedere NP-completo e Marek Karpinski

NP-completo

Nella teoria della complessità computazionale i problemi NP-completi sono i più difficili problemi nella classe NP ("problemi risolvibili non-deterministicamente in tempo polinomiale") nel senso che, se si trovasse un algoritmo in grado di risolvere "velocemente" (nel senso di utilizzare tempo polinomiale) un qualsiasi problema NP-completo, allora si potrebbe usarlo per risolvere "velocemente" ogni problema in NP.

Vedere NP-completo e NP-completo

NP-difficile

In teoria della complessità, i problemi NP-difficili o NP-ardui (da nondetermistic polynomial-time hard problem, "problema difficile non deterministico in tempo polinomiale") sono una classe di problemi che può essere definita informalmente come la classe dei problemi almeno difficili come i più difficili problemi delle classi di complessità P e NP.

Vedere NP-completo e NP-difficile

Numero intero

Il simbolo dell'insieme dei numeri interi I numeri interi (o numeri interi relativi o, semplicemente, numeri relativi) corrispondono all'insieme ottenuto unendo i numeri naturali (0, 1, 2,...) e i numeri interi negativi (−1, −2, −3,...), cioè quelli ottenuti ponendo un segno “−” davanti ai naturali.

Vedere NP-completo e Numero intero

Problema del commesso viaggiatore

Il problema del commesso viaggiatore è il più semplice fra i problemi di instradamento e di gestione dei processi. Viene spesso indicato con il suo nome inglese, traveling salesman problem o traveling salesperson problem, in acronimo TSP.

Vedere NP-completo e Problema del commesso viaggiatore

Problema della cricca

In informatica, il problema della cricca si riferisce a uno qualsiasi dei problemi legati alla ricerca di particolari sottografi completi ("cricche") in un grafo, cioè, insiemi di elementi dove ciascuna coppia di elementi è connessa.

Vedere NP-completo e Problema della cricca

Problema delle somme parziali

Il problema delle somme parziali è uno dei problemi NP-completi. Esso consiste nel determinare, dato un insieme finito di numeri interi, se ne esiste un sottoinsieme tale che la somma di suoi elementi sia 0.

Vedere NP-completo e Problema delle somme parziali

Problema dello zaino

Il problema dello zaino, o, è un problema di ottimizzazione combinatoria posto nel modo seguente.

Vedere NP-completo e Problema dello zaino

Problema di copertura dei vertici

Il problema di copertura dei vertici, detto anche in inglese vertex cover, appartiene alla classe di equivalenza dei più difficili problemi risolvibili non-deterministicamente in tempo polinomiale, assieme al problema del commesso viaggiatore, il knapsack problem, ecc.

Vedere NP-completo e Problema di copertura dei vertici

Reduced instruction set computer

Reduced Instruction Set Computer (RISC), nell'elettronica digitale, indica un'architettura per microprocessori che predilige lo sviluppo di un'architettura semplice e lineare.

Vedere NP-completo e Reduced instruction set computer

Richard Karp

Nel 1972 ha pubblicato un elenco di 21 problemi NP-completi. Ha vinto il Premio Turing nel 1985 ed il Premio Kyōto per la tecnologia nel 2008.

Vedere NP-completo e Richard Karp

Ronald Rivest

Il suo lavoro più noto è il sistema di crittografia asimmetrica che ha sviluppato assieme a Leonard Adleman e Adi Shamir: il crittosistema RSA (1978).

Vedere NP-completo e Ronald Rivest

Se e solo se

In matematica, filosofia, logica e nei campi tecnici che ne dipendono, si usa spesso l'espressione se e solo se, o l'abbreviazione sse, per esprimere l'equivalenza logica di due enunciati, esplicitando che i due enunciati hanno lo stesso valore di verità: se è vero il secondo allora è vero anche il primo, e viceversa.

Vedere NP-completo e Se e solo se

Soddisfacibilità booleana

La soddisfacibilità booleana, o soddisfacibilità proposizionale o SAT, è il problema di determinare se una formula booleana è soddisfacibile o insoddisfacibile.

Vedere NP-completo e Soddisfacibilità booleana

Teorema di Cook-Levin

Nella teoria della complessità algoritmica, il teorema di Cook-Levin, dimostrato da Stephen Cook nel suo articolo "Complessità delle Procedure di Dimostrazione dei Teoremi" ("The Complexity of Theorem Proving Procedures") del 1971, afferma che il problema di soddisfacibilità booleana è NP-completo.

Vedere NP-completo e Teorema di Cook-Levin

Teoria dei grafi

In matematica, informatica e, più in particolare, geometria combinatoria, la teoria dei grafi è la disciplina che si occupa dello studio dei grafi, oggetti discreti che permettono di schematizzare una grande varietà di situazioni e processi, e spesso di consentirne delle analisi in termini quantitativi e algoritmici.

Vedere NP-completo e Teoria dei grafi

Teoria della complessità computazionale

La teoria della complessità computazionale è una branca della teoria della computabilità che studia le risorse minime necessarie (principalmente tempo di calcolo e memoria) per la risoluzione di un problema.

Vedere NP-completo e Teoria della complessità computazionale

Thomas H. Cormen

Coautore del libro Introduction to Algorithms (Introduzione agli algoritmi), con Charles Leiserson, Ron Rivest, e Cliff Stein, è professore di informatica al Dartmouth College.

Vedere NP-completo e Thomas H. Cormen

Università di Liverpool

L'Università di Liverpool (in inglese: University of Liverpool) è un'università pubblica del Regno Unito, situata a Liverpool, in Inghilterra; nota per essere una delle sei red brick university, le università fondate nel XIX secolo nelle maggiori città britanniche.

Vedere NP-completo e Università di Liverpool

Vedi anche

Classi di complessità

Ottimizzazione

Problemi NP-completi

Conosciuto come NP-Completezza.