Discussione:NP-difficile

Ultimo commento: 15 anni fa, lasciato da Moongateclimber in merito all'argomento Problema della fermata

Problema della fermata

modifica

Non ho modificato perchè non sono un esperto, ma che io sappia il passaggio dove dice

Ci sono problemi decisionali che sono NP-difficili ma non NP-completi, e a questa categoria appartiene il celebre problema della fermata: dato un programma (o una macchina di Turing) e l'insieme dei dati che gli verranno forniti in ingresso, stabilire se il programma terminerà.

Per quel che ne so, il problema della fermata non è nè NP-hard nè NP-completo, è semplicemente non calcolabile, nel senso che non esiste un algoritmo che lo risolva.

Lì per lì avevo apportato la correzione, ma in effetti non è così ovvio. Un problema non deve essere decidibile per essere NP-hard (vedi definizione esatta). Anche en:NP-hard riporta il problema dell'arresto come NP-hard. Io queste cose le ho studiate qualche anno fa :-) se c'è qualcuno fresco di esame che può confermare, ben venga... Moongateclimber (msg) 06:56, 28 nov 2008 (CET)Rispondi

Siamo freschi d'esame e possiamo confermare che la frase riportata sopra è priva di ogni veridicità! Il problema della fermata è del tutto incalcolabile ( ed è tra l'altro uno dei più importanti problemi incalcolabili! ) Sarebbe il caso di modificare la pagina!

esempio "sospetto"

modifica

nella sezione esempi: "dato un insieme di interi, c'è almeno un suo sottoinsieme che ha come somma algebrica zero" viene riportato come un esempio di NP-hard. Il che credo sia quasi sicuramente falso, dato che verificare se il sottoinsieme che restituisce sia una soluzione valida è "facile". Quindi dovrebbe essere un problema NP

sono sempre io.. http://en.wikipedia.org/wiki/Subset_sum_problem conferma che è NP. ora non ho tempo di registrarmi se qualcuno intanto vuole toglierlo - o perlomeno specificare che è ANCHE NP ma sinceramente credo crei confusione...

Ritorna alla pagina "NP-difficile".