l'accesso più veloce di browser!
43 relazioni: Algoritmo, Algoritmo greedy, Cambridge (Massachusetts), Cammino hamiltoniano, Classe di complessità, Classi di complessità P e NP, Co-NP, Colorazione dei grafi, Complemento (complessità), Gioco del quindici, Grafo, Insieme, Insieme indipendente (teoria dei grafi), Introduzione agli algoritmi, Isomorfismo, Isomorfismo di sottografi, Istituto matematico Clay, John Hopcroft, Lingua inglese, Linguaggio formale, Marek Karpinski, NP-completo, NP-difficile, Numero intero, P (complessità), 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, Stephen Cook, Teorema di Cook-Levin, Teoria dei grafi, Teoria della complessità computazionale, Thomas H. Cormen, Università di Liverpool, 1971, 1979.
Algoritmo
Un algoritmo è un procedimento che risolve un determinato problema attraverso un numero finito di passi elementari in un tempo ragionevole.
Nuovo!!: NP-completo e Algoritmo · Mostra di più »
Algoritmo greedy
Un algoritmo greedy è un algoritmo che cerca di ottenere una soluzione ottima da un punto di vista globale attraverso la scelta della soluzione più golosa (aggressiva o avida, a seconda della traduzione preferita del termine greedy dall'inglese) ad ogni passo locale.
Nuovo!!: NP-completo e Algoritmo greedy · Mostra di più »
Cambridge (Massachusetts)
Cambridge è una città degli Stati Uniti d'America, capoluogo insieme a Lowell della contea di Middlesex nello stato del Massachusetts.
Nuovo!!: NP-completo e Cambridge (Massachusetts) · Mostra di più »
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.
Nuovo!!: NP-completo e Cammino hamiltoniano · Mostra di più »
Classe di complessità
Nella teoria della complessità computazionale, una classe di complessità è un insieme di problemi di una certa complessità.
Nuovo!!: NP-completo e Classe di complessità · Mostra di più »
Classi di complessità P e NP
Il problema delle classi P e NP è un problema tuttora aperto nella teoria della complessità computazionale.
Nuovo!!: NP-completo e Classi di complessità P e NP · Mostra di più »
Co-NP
Nella teoria della complessità computazionale, coNP è la classe di problemi complementari a quelli della classe NP.
Nuovo!!: NP-completo e Co-NP · Mostra di più »
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.
Nuovo!!: NP-completo e Colorazione dei grafi · Mostra di più »
Complemento (complessità)
Nella teoria della complessità computazionale, il complemento di un problema decisionale è il problema risultante dall'inversione delle risposte sì e no.
Nuovo!!: NP-completo e Complemento (complessità) · Mostra di più »
Gioco del quindici
Il gioco del quindici è un rompicapo classico creato nel 1874 da Noyes Palmer Chapman, postino in servizio a Canastota, e popolarizzato nel 1880 da Samuel Loyd.
Nuovo!!: NP-completo e Gioco del quindici · Mostra di più »
Grafo
Grafo (non orientato) con 6 nodi e 5 archi I grafi sono strutture matematiche discrete che rivestono interesse sia per la matematica che per un'ampia gamma di campi applicativi.
Nuovo!!: NP-completo e Grafo · Mostra di più »
Insieme
In matematica, un raggruppamento di oggetti rappresenta un insieme se esiste un criterio oggettivo che permette di decidere univocamente se un qualunque oggetto fa parte o no del raggruppamento.
Nuovo!!: NP-completo e Insieme · Mostra di più »
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.
Nuovo!!: NP-completo e Insieme indipendente (teoria dei grafi) · Mostra di più »
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.
Nuovo!!: NP-completo e Introduzione agli algoritmi · Mostra di più »
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.
Nuovo!!: NP-completo e Isomorfismo · Mostra di più »
Isomorfismo di sottografi
Nella teoria della complessità computazionale, l'isomorfismo di sottografo è un problema decisionale di tipo NP-completo.
Nuovo!!: NP-completo e Isomorfismo di sottografi · Mostra di più »
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.
Nuovo!!: NP-completo e Istituto matematico Clay · Mostra di più »
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à).
Nuovo!!: NP-completo e John Hopcroft · Mostra di più »
Lingua inglese
L'inglese (nome nativo English) è una lingua indoeuropea appartenente al ramo occidentale delle lingue germaniche, assieme all'olandese, all'alto e basso tedesco, al fiammingo e al frisone.
Nuovo!!: NP-completo e Lingua inglese · Mostra di più »
Linguaggio formale
Per linguaggio formale, in matematica, logica, informatica e linguistica, si intende un insieme di stringhe di lunghezza finita costruite sopra un alfabeto finito, cioè sopra un insieme finito di oggetti tendenzialmente semplici che vengono chiamati caratteri, simboli o lettere.
Nuovo!!: NP-completo e Linguaggio formale · Mostra di più »
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.
Nuovo!!: NP-completo e Marek Karpinski · Mostra di più »
NP-completo
Nella teoria della complessità computazionale i problemi NP-completi sono i più difficili problemi nella classe NP ("problemi non deterministici 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.
Nuovo!!: NP-completo e NP-completo · Mostra di più »
NP-difficile
In teoria della complessità, i problemi NP-difficili o NP-ardui (in inglese NP-hard, 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.
Nuovo!!: NP-completo e NP-difficile · Mostra di più »
Numero intero
I numeri interi (o numeri interi relativi o, semplicemente, numeri relativi) sono formati dall'unione dei numeri naturali (0, 1, 2,...) e dei numeri interi negativi (−1, −2, −3,...), costruiti ponendo un segno “−” davanti ai naturali.
Nuovo!!: NP-completo e Numero intero · Mostra di più »
P (complessità)
Nella teoria della complessità computazionale, P, anche conosciuto come PTIME o DTIME(nO(1)), è una delle più importanti classi di complessità.
Nuovo!!: NP-completo e P (complessità) · Mostra di più »
Problema del commesso viaggiatore
Il problema del commesso viaggiatore è il più semplice fra i problemi di routing e di scheduling.
Nuovo!!: NP-completo e Problema del commesso viaggiatore · Mostra di più »
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.
Nuovo!!: NP-completo e Problema della cricca · Mostra di più »
Problema delle somme parziali
Il problema delle somme parziali è uno dei problemi NP-completi.
Nuovo!!: NP-completo e Problema delle somme parziali · Mostra di più »
Problema dello zaino
In questo caso, la soluzione è di mettere nello zaino tre scatole gialle e tre grigie Il problema dello zaino, detto anche Knapsack problem, è un problema di ottimizzazione combinatoria posto nel modo seguente.
Nuovo!!: NP-completo e Problema dello zaino · Mostra di più »
Problema di copertura dei vertici
Il problema di copertura dei vertici, detto anche in inglese vertex cover, appartiene alla classe di equivalenza dei problemi completi non deterministici, assieme al problema del commesso viaggiatore, il knapsack problem, ecc.
Nuovo!!: NP-completo e Problema di copertura dei vertici · Mostra di più »
Reduced instruction set computer
L'acronimo RISC, dall'inglese Reduced Instruction Set Computer, indica una filosofia di progettazione di architetture per microprocessori che predilige lo sviluppo di un'architettura semplice e lineare.
Nuovo!!: NP-completo e Reduced instruction set computer · Mostra di più »
Richard Karp
Nel 1972 ha pubblicato un elenco di 21 problemi NP-completi.
Nuovo!!: NP-completo e Richard Karp · Mostra di più »
Ronald Rivest
Il suo lavoro più noto è sicuramente il sistema di crittografia asimmetrica che ha sviluppato assieme a Leonard Adleman e Adi Shamir: il crittosistema RSA (1978).
Nuovo!!: NP-completo e Ronald Rivest · Mostra di più »
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.
Nuovo!!: NP-completo e Se e solo se · Mostra di più »
Soddisfacibilità booleana
La soddisfacibilità booleana, o soddisfacibilità proposizionale o SAT, è il problema di determinare se una formula booleana è soddisfacibile o insoddisfacibile.
Nuovo!!: NP-completo e Soddisfacibilità booleana · Mostra di più »
Stephen Cook
Nessuna descrizione.
Nuovo!!: NP-completo e Stephen Cook · Mostra di più »
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.
Nuovo!!: NP-completo e Teorema di Cook-Levin · Mostra di più »
Teoria dei grafi
In matematica, informatica e, più in particolare, geometria combinatoria, la teoria dei grafi si occupa di studiare i grafi, che sono oggetti discreti che permettono di schematizzare una grande varietà di situazioni e di processi e spesso di consentirne delle analisi in termini quantitativi e algoritmici.
Nuovo!!: NP-completo e Teoria dei grafi · Mostra di più »
Teoria della complessità computazionale
In informatica, 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.
Nuovo!!: NP-completo e Teoria della complessità computazionale · Mostra di più »
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.
Nuovo!!: NP-completo e Thomas H. Cormen · Mostra di più »
Università di Liverpool
L'Università di Liverpool è un'università pubblica del Regno Unito, situata a Liverpool, in Inghilterra.
Nuovo!!: NP-completo e Università di Liverpool · Mostra di più »
1971
Nessuna descrizione.
Nuovo!!: NP-completo e 1971 · Mostra di più »
1979
Nessuna descrizione.
Nuovo!!: NP-completo e 1979 · Mostra di più »
Riorienta qui:
NP-Completezza, NP-Completo, NP-completezza.
