l'accesso più veloce di browser!
24 relazioni: Algoritmo di approssimazione, BPP (complessità), Classe di complessità, Classi di complessità P e NP, Co-NP-completo, Complemento (complessità), Complessità temporale, E (complessità), EXPTIME, L'arte della guerra, Ottimizzazione (matematica), P (complessità), Problema computazionale, Problema del commesso viaggiatore, Problema del flusso di costo minimo, Problema della cricca, Problema di funzione, Problema di ottimizzazione, Ricerca operativa, RP (complessità), Sharp-P, Taglio massimo, Teorema di Cook-Levin, 2-EXPTIME.
Algoritmo di approssimazione
Nell'informatica e nella ricerca operativa, un algoritmo di approssimazione è un algoritmo usato per trovare soluzioni approssimate a problemi di ottimizzazione.
Nuovo!!: Problema decisionale e Algoritmo di approssimazione · Mostra di più »
BPP (complessità)
Nella teoria della complessità computazionale, BPP (Bounded-error Probabilistic Polynomial time, "tempo polinomiale probabilistico con errore limitato") è una classe di complessità a cui appartengono quei problemi decisionali che richiedono un tempo polinomiale per avere una soluzione probabilistica corretta.
Nuovo!!: Problema decisionale e BPP (complessità) · Mostra di più »
Classe di complessità
Nella teoria della complessità computazionale, una classe di complessità è un insieme di problemi di una certa complessità.
Nuovo!!: Problema decisionale 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!!: Problema decisionale e Classi di complessità P e NP · Mostra di più »
Co-NP-completo
Nella teoria della complessità computazionale, i problemi computazionali che sono co-NP-completi sono i problemi più difficili in co-NP, nel senso che sono quelli che hanno le maggiori probabilità di non essere in P. Se esiste un modo di risolvere rapidamente un problema co-NP-completo, allora quell'algoritmo può essere usato per risolvere rapidamente tutti i problemi co-NP.
Nuovo!!: Problema decisionale e Co-NP-completo · 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!!: Problema decisionale e Complemento (complessità) · Mostra di più »
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.
Nuovo!!: Problema decisionale e Complessità temporale · Mostra di più »
E (complessità)
Nella teoria della complessità computazionale, la classe di complessità E è l'insieme di problemi decisionali che possono essere risolti da una macchina deterministica di Turing nel tempo 2O(n) ed è perciò uguale alla classe di complessità DTIME(2O(n)).
Nuovo!!: Problema decisionale e E (complessità) · Mostra di più »
EXPTIME
Nella teoria della complessità computazionale la classe di complessità EXPTIME (a volte chiamata EXP, da Exponential Time, "tempo esponenziale"), è l'insieme di tutti i problemi decisionali risolvibili da una macchina deterministica di Turing nel tempo O(2p(n)), dove p(n) è una funzione polinomiale di n. In termini di DTIME, Sappiamo che e inoltre, dal teorema della gerarchia temporale e dal teorema della gerarchia spaziale, che così almeno una delle prime tre inclusioni e almeno una delle ultime tre inclusioni deve essere corretta, ma non si sa quali sono, anche se la maggior parte degli esperti credono che tutte le inclusioni siano corrette.
Nuovo!!: Problema decisionale e EXPTIME · Mostra di più »
L'arte della guerra
L'arte della guerra (Sūnzǐ Bīngfǎ, 孫子兵法) è un trattato di strategia militare attribuito, a seguito di una tradizione orale lunga almeno due secoli, al generale Sunzi (in cinese: 孫子; pinyin: Sūnzǐ; Wade-Giles: Sun Tzu), vissuto in Cina probabilmente fra il VI e il V secolo a.C. Importante è stato il ritrovamento di un manoscritto in lingua originale scritto su un rotolo di bambù intorno al III secolo a.C. Si tratta probabilmente del più antico testo di arte militare esistente (VI secolo a.C. circa).
Nuovo!!: Problema decisionale e L'arte della guerra · Mostra di più »
Ottimizzazione (matematica)
L'ottimizzazione (o programmazione matematica, PM) è una branca della matematica applicata che studia teoria e metodi per la ricerca dei punti di massimo e minimo di una funzione matematica; si ottiene così un modello matematico che traduce in termini matematici un dato problema (non occupandosi quindi direttamente di come tale modello sia stato costruito).
Nuovo!!: Problema decisionale e Ottimizzazione (matematica) · 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!!: Problema decisionale e P (complessità) · Mostra di più »
Problema computazionale
Nell'informatica teorica, un problema computazionale o problema astratto è una relazione tra un insieme di istanze e un insieme di soluzioni.
Nuovo!!: Problema decisionale e Problema computazionale · Mostra di più »
Problema del commesso viaggiatore
Il problema del commesso viaggiatore è il più semplice fra i problemi di routing e di scheduling.
Nuovo!!: Problema decisionale e Problema del commesso viaggiatore · Mostra di più »
Problema del flusso di costo minimo
Il problema del flusso di costo minimo (minimum-cost flow problem, abbreviato MCFP) è un problema di decisione e ottimizzazione che consiste nel trovare il modo meno costoso possibile di far passare un certo ammontare di flusso tramite una rete di flusso.
Nuovo!!: Problema decisionale e Problema del flusso di costo minimo · 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!!: Problema decisionale e Problema della cricca · Mostra di più »
Problema di funzione
Nella teoria della complessità computazionale, un problema di funzione è un problema computazionale dove ci si aspetta una singola uscita (di una funzione totale) per ogni entrata, ma l'uscita è più complessa di quello di un problema di decisione, cioè, non è solo "SÌ" o "NO".
Nuovo!!: Problema decisionale e Problema di funzione · Mostra di più »
Problema di ottimizzazione
In matematica e in informatica, un problema di ottimizzazione è il problema di trovare la migliore soluzione fra tutte le soluzioni fattibili.
Nuovo!!: Problema decisionale e Problema di ottimizzazione · Mostra di più »
Ricerca operativa
La ricerca operativa (nota anche come teoria delle decisioni, scienza della gestione o, in inglese, operations research ("Operational Research" in Europa) e indicata con le sigle RO o OR) è la branca della matematica applicata in cui problemi decisionali complessi vengono analizzati e risolti mediante modelli matematici e metodi quantitativi avanzati (ottimizzazione, simulazione, ecc.). L'obiettivo è quello di fornire un supporto alla presa di decisioni.
Nuovo!!: Problema decisionale e Ricerca operativa · Mostra di più »
RP (complessità)
Nella teoria della complessità computazionale, RP (Randomized Polynomial time, "tempo polinomiale randomizzato") è la classe di complessità dei problemi decisionali eseguiti su una macchina di Turing probabilistica.
Nuovo!!: Problema decisionale e RP (complessità) · Mostra di più »
Sharp-P
Nella teoria della complessità computazionale, la classe di complessità #P (pronunciata "sharp P" o, a volte, "numero P" o "cancelletto P") è l'insieme dei problemi di conteggio associati ai problemi decisionali nell'insieme NP.
Nuovo!!: Problema decisionale e Sharp-P · Mostra di più »
Taglio massimo
In un grafo, un taglio massimo è un taglio di dimensione almeno pari a quella di tutti gli altri tagli.
Nuovo!!: Problema decisionale e Taglio massimo · 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!!: Problema decisionale e Teorema di Cook-Levin · Mostra di più »
2-EXPTIME
Nella teoria della complessità computazionale, la classe di complessità 2-EXPTIME (talvolta chiamata 2-EXP, da 2-Exponential Time, "tempo 2-esponenziale") è l'insieme di tutti i problemi decisionali risolvibili da una macchina deterministica di Turing nel tempo O(22p(n)), dove p(n) è una funzione polinomiale di n. In termini di DTIME, Sappiamo che 2-EXPTIME può anche essere riformulato come la classe di spazio AEXPSPACE, i problemi che possono essere risolti da una macchina di Turing alternante in spazio esponenziale.
Nuovo!!: Problema decisionale e 2-EXPTIME · Mostra di più »
