NP-completezza
Qualcuno mi sa dire quali sono i passi necessari per dimostrare l'NP-completezza di un problema P?
Risposte
Ciao,
secondo me è meglio che riformuli la domanda.
Intendi (i passi per):
- dimostrare che un problema è NP-complete (perciò appartiene all'insieme NP)
- un problema che appartiene a P e dimostrare che appartiene anche ad NP
PS: questo sarebbe più una questione di Informatica (Teorica).
"One":
Qualcuno mi sa dire quali sono i passi necessari per dimostrare l'NP-completezza di un problema P?
secondo me è meglio che riformuli la domanda.
Intendi (i passi per):
- dimostrare che un problema è NP-complete (perciò appartiene all'insieme NP)
- un problema che appartiene a P e dimostrare che appartiene anche ad NP
PS: questo sarebbe più una questione di Informatica (Teorica).
Mi servirebbe una buona definizione di problema NP-completo.Inoltre dovrei anche dimostrare che il problema del Vertex Cover appartiene a gli NP-completi
"One":
Qualcuno mi sa dire quali sono i passi necessari per dimostrare l'NP-completezza di un problema P?
La vedo difficile...
"One":
Mi servirebbe una buona definizione di problema NP-completo.Inoltre dovrei anche dimostrare che il problema del Vertex Cover appartiene a gli NP-completi
Questa è cosa assai diversa. Informalmente, un problema (ma io preferisco parlare di linguaggio) è NP-completo se appartiene a NP e ogni altro in NP è polinomialmente riducibile ad esso.
Per il Vertex Cover, puoi provare una riduzione da 3SAT (spero tu sappia di cosa parlo).
[ Effettivamente, in Informatica stava meglio ]
un problema (ma io preferisco parlare di linguaggio)
Quale è la differenza tra linguaggio e problema?
Nessuno sa dirmi la differenza?.....Non ci credo
Non sai cercarla da te su internet o, ancora meglio, su un libro?.....Non ci credo
Quando scrivo in questo forum lo faccio perchè non ho trovato niente di esaustivo ne sul libro,ne su Internet.Ritornando sull'argomento:ho visto che spesso viene usato il termine linguaggio altre volte invece il termine problema,e se ho ben capito non sono la stessa cosa.
"One":
ho visto che spesso viene usato il termine linguaggio altre volte invece il termine problema,e se ho ben capito non sono la stessa cosa.
se vuoi una piccola introduzione informale su questo tema (linguaggio vs. problema):
- linguaggio: capitolo 2. Una prima classificazione
- problema: http://profs.sci.univr.it/%7Eposenato/c ... one.pdf.gz
penso ti sia utile.
Allora, il problema np, è un problema relativo,(mi scuso anticipatamente se non sarò corretto nell' esposizione ma è un problema che ho toccato solo marginalmente)
In se un problema è np se aumentano i costi di calcolo al crescere del problema.
Riassunto dato che le variabili aumentano con l' aumentare della complessità del problema aumenta il costo di calcolo.
Ora la questione è riducibile nella sua forma più semplice(senza quindi far intervenire sistemi di equazioni di funzioni integrali e di derivate o ellittiche), nella forma della funzione polinomiale ad una variabile.
Dimostrare quindi l' aumento della complessità delle suddette implica un aumento del sistema di funzioni polinomiali.
Però la sua risolvibilità nel senso cioè se il problema è effettivamente un np, è un discorso a parte.
Prendiamo il crivello di eratostene in teoria dei numeri che elimina i multipli. Se implichiamo solo questo tipo di funzioni, nello stabilire la qualità di primo di un numero i costi di fattorizzazione di n crescono al crescere di n stesso.
Ma questo implica che questo sia l' unico modo di determinarlo, entro certi modelli. Come ad esempio può essere un numero irrazionale, trascendentale etc... Ma riprendiamo i numeri primi. Questo non può necessariamente escludere che non esista una soluzione definitiva, che non comporta costi di calcolo. Prendiamo l' ipotesi di Riemann, se fosse dimostrata basterebbe guardare l' appartenenza dello zero con parte reale 1/2, per stabilire se lo è o meno.
Difatti dovrebbe essere uno dei problemi del millennio. Fra l' altro uno dei più affascinanti, questo però implica la sterilità del problema in se, in quanto un np per cui esistono f(x), infinite, non necessariamente è un np. Spero di non aver commesso errori nello spiegare il mio pensiero, e se l' ho fatto mi scuso.
In se un problema è np se aumentano i costi di calcolo al crescere del problema.
Riassunto dato che le variabili aumentano con l' aumentare della complessità del problema aumenta il costo di calcolo.
Ora la questione è riducibile nella sua forma più semplice(senza quindi far intervenire sistemi di equazioni di funzioni integrali e di derivate o ellittiche), nella forma della funzione polinomiale ad una variabile.
Dimostrare quindi l' aumento della complessità delle suddette implica un aumento del sistema di funzioni polinomiali.
Però la sua risolvibilità nel senso cioè se il problema è effettivamente un np, è un discorso a parte.
Prendiamo il crivello di eratostene in teoria dei numeri che elimina i multipli. Se implichiamo solo questo tipo di funzioni, nello stabilire la qualità di primo di un numero i costi di fattorizzazione di n crescono al crescere di n stesso.
Ma questo implica che questo sia l' unico modo di determinarlo, entro certi modelli. Come ad esempio può essere un numero irrazionale, trascendentale etc... Ma riprendiamo i numeri primi. Questo non può necessariamente escludere che non esista una soluzione definitiva, che non comporta costi di calcolo. Prendiamo l' ipotesi di Riemann, se fosse dimostrata basterebbe guardare l' appartenenza dello zero con parte reale 1/2, per stabilire se lo è o meno.
Difatti dovrebbe essere uno dei problemi del millennio. Fra l' altro uno dei più affascinanti, questo però implica la sterilità del problema in se, in quanto un np per cui esistono f(x), infinite, non necessariamente è un np. Spero di non aver commesso errori nello spiegare il mio pensiero, e se l' ho fatto mi scuso.
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo