So che P = NP non è stato risolto fino ad ora, ma qualcuno può dirmi qualcosa su quanto segue: Quali sono attualmente i metodi matematici/informatici più promettenti che potrebbero essere utili per affrontare questo problema? O forse nessuno di questi metodi è potenzialmente utile fino ad ora? C'è qualche compendio (gratuito) su questo argomento in cui posso trovare tutte/la maggior parte delle ricerche fatte in quest'area?P = NP: quali sono i metodi più promettenti?
8
A
risposta
7
Un'eccellente panoramica è apparso lo scorso anno nella Comunicazione dell'ACM. Penso che sia diventato l'articolo più scaricato di CACM di sempre, quindi la tua domanda potrebbe essere rilevante dopo tutto :-)
The Status of the P=NP Problem, Lance Fortnow, comunicazioni di ACM, vol. 52 n. 9, 2009
+1
Grazie. Questo è esattamente il tipo di informazioni che stavo cercando. – phimuemue
Problemi correlati
- 1. P! = NP domanda
- 2. I problemi NP-hard che non sono NP-completi sono più difficili?
- 3. Quali sono i metodi Html.Validate e Html.ValidateFor?
- 4. Quali sono i plugin Xcode più utili?
- 5. Quali sono i diversi metodi per iniettare preoccupazioni trasversali?
- 6. Quali sono i metodi di riordino validi per Java sincronizzati?
- 7. Quali sono le regole per gestire i metodi ereditati dall'omonimo?
- 8. ASP.NET MVC: quali sono i metodi di azione? Azione Risultato? Come sono collegati?
- 9. Quali sono i problemi "più difficili" utilizzando il tempo polinomiale?
- 10. Quali sono i metodi più avanzati per la risoluzione di equazioni funzionali?
- 11. Quali sono i metodi più semplici/migliori per la gestione dei file di tag ctags?
- 12. I metodi LINQ sono metodi di estensione?
- 13. Perché più istanze dell'oggetto Method sono per i metodi ereditati
- 14. Quali strumenti sono disponibili per visualizzare quali metodi chiamano altri metodi per il codice Java?
- 15. I metodi astratti sono virtuali?
- 16. Quali sono i pacchetti intelligenti più utili per Meteor.js
- 17. Quali sono i metodi di accesso "primitivi" per i dati principali?
- 18. I metodi asincroni dell'applicazione Mvc sono sospesi
- 19. Sono "div> p" e "div p" uguali?
- 20. Quali sono questi parametri extra nei miei metodi proxy ASMX?
- 21. Tutti i metodi di interfaccia sono astratti?
- 22. Quali sono i vantaggi delle diverse endianness?
- 23. Quali sono i modi più idiomatici per combinare i tensori nella torcia?
- 24. Quali sono i vantaggi dell'utilizzo di automapper?
- 25. Come determinare quali rapporti sono più vicini
- 26. Quali sono le librerie Java più importanti?
- 27. Quali sono le differenze tra funzioni e metodi in Swift?
- 28. Quali sono i migliori componenti di Boost?
- 29. Quali metodi sono disponibili per arrestare più postback di un modulo in ASP.NET MVC?
- 30. Quali sono questi misteriosi metodi di un'eccezione javascript?
Nitpic: hai scritto P meno NP. La grande domanda è se P = NP (P è uguale a NP). Spesso scritto come P = NP? Il primo sottoinsieme promettente è considerare solo i problemi NP-completi, non tutti i problemi NP. Suggerisco di riformulare la domanda per trattare solo i problemi NP-completi. – abelenky
Soggettivo e fuori tema, mi dispiace. Non ti insulterò con gli ovvi suggerimenti su dove guardare invece di qui. – bmargulies
@bmargulies: come è questo fuori tema? – sepp2k