Informatica e NP-completo

Scorciatoie: Differenze, Analogie, Jaccard somiglianza Coefficiente, Riferimenti.

Differenza tra Informatica e NP-completo

Informatica vs. NP-completo

Linformatica è la scienza o disciplina che si occupa del trattamento dell'informazione mediante procedure automatizzate, avendo in particolare per oggetto lo studio dei fondamenti teorici dell'informazione, della sua computazione a livello logico e delle tecniche pratiche per la sua implementazione e applicazione in sistemi elettronici automatizzati detti quindi sistemi informatici; come tale è una disciplina fortemente connessa con la logica matematica, l'automatica, l'elettronica e anche l'elettromeccanica. 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.

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.

Algoritmo e Informatica · Algoritmo e NP-completo · 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. 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).

Classi di complessità P e NP e Informatica · Classi di complessità P e NP e NP-completo · Mostra di più »

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.

Informatica e Macchina di Turing · Macchina di Turing e NP-completo · Mostra di più »

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.

Informatica e NP-difficile · NP-completo e NP-difficile · Mostra di più »

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.

Informatica e Teoria della complessità computazionale · NP-completo e Teoria della complessità computazionale · Mostra di più »