NP-completezza
Pubblicato da ZeroKnowledge su martedì, 6 febbraio 2007
Certo, perchè no:
Il problema 3-clicque è un problema di classe NPC. Sull’appartenenza della classe P non possiamo dire nulla, ci troviamo difronte a una questione aperta, al momento non ci sono problemi di classe NPC risolvibili in tempo polinomiale, si dimostrerebbe anche che: P=NP=NPC. Non possiamo dire nulla nemmeno sull’appartenenza alla classe CO-NP perchè un’altra questione aperta è la seguente: se LєNPC non sappiamo che LєNP (L segnato).
mario detto
nooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooo help US!!!
ZeroKnowledge detto
HUAhuAUHAHUhuhua.
Però pensandoci io una soluzione ce l’avrei: cambiamo facoltà e non avremo più a che fare con sta roba!
P.S.
Sant’Alfredo prega per noi!
mario detto
no fuggire è da codardi
ZeroKnowledge detto
Bravissimo, hai ragione. Noi siamo superiori…ci metteremo 10 anni ma non importa
Vabbè tanto se non è domani è il 26…st’esame sadda passa’ :/
AHAHahhahAHAHAH
ZeroKnowledge detto
Aggiungo inoltre:
CLASSI DI COMPLESSITA’ P
E’ l’insieme dei linguaggi tali che esiste un algoritmo che decide L in un tempo O(n^k). Un algoritmo A decide L in un tempo polinomiale se per ogni x є L si ha A(x)=1 in un tempo O(n^k) e se per ogni x є ∑*- L avremo A(x)=0 in un tempo O(n^k).
P.S.
Altro che ingeGNEGNEri… noi li usiamo per lavori di sotto-scrivania.
Daniel Pan detto
Blà blà blà -.-
ambimbMam detto
This is really cool… I want make the best use of my definite bench A joke for you! Where did King Tut go to ease his back pain? The Cairo-practor!