Discussione:NP-difficile

Problema della fermata

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)

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"

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...