Indice
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.
- Classi di complessità
- Ottimizzazione
- 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à
- 2-EXPTIME
- AC (complessità)
- AC0
- ACC0
- Classe di complessità
- Co-NP
- Co-NP-completo
- DLOGTIME
- E (complessità)
- EXPSPACE
- EXPTIME
- Gerarchia esponenziale
- L (complessità)
- Lista delle classi di complessità
- NC (complessità)
- NL (complessità)
- NP (complessità)
- NP-Intermedio
- NP-completo
- NP-difficile
- P (complessità)
- PSPACE
- PSPACE-completo
- Schema di approssimazione in tempo polinomiale
- Tempo pseudopolinomiale
Ottimizzazione
- Classi di complessità P e NP
- Compressed sensing
- Condizioni di Karush-Kuhn-Tucker
- Controllo ottimo
- Direzione di discesa
- Discesa del gradiente
- ELECTRE
- Funzione pseudo-booleana
- Massimo e minimo di una funzione
- Metodo dei moltiplicatori di Lagrange
- NP-completo
- Numero poligonale centrale
- Ottimizzazione (matematica)
- Ottimizzazione convessa
- Ottimo paretiano
- Procedura-S
- Teorema del minimax
- Teoria della scelta sociale
Problemi NP-completi
- 21 problemi NP-completi di Karp
- Cammino hamiltoniano
- Campo minato (videogioco)
- Colorazione dei grafi
- Copertura dei vertici
- Criptaritmo
- Freecell
- Gioco del quindici
- Grafo di dischi
- Hitori
- Insieme indipendente (teoria dei grafi)
- Isomorfismo di sottografi
- Kakuro
- Mah Jong (solitario)
- Massima sottosequenza comune
- Mastermind
- Masyu
- Matematica degli origami
- Modello di Ising
- NP-completo
- Nonogram
- Nurikabe (gioco)
- Omeomorfismo (teoria dei grafi)
- Problema del commesso viaggiatore
- Problema del postino cinese
- Problema della cricca
- Problema dello zaino
- Problema di copertura delle cricche
- Problema di soddisfacimento di vincoli
- Residuo quadratico
- Reverse engineering
- SameGame
- Slitherlink
- Soddisfacibilità booleana
- Sokoban
- Solitario della Bastiglia
- Sudoku
- Taglio massimo
- Tetris
- Vehicle routing problem
Conosciuto come NP-Completezza.