Archivio Istituzionale della RicercaThe analysis discussed in this paper is based on a well‐known NP‐complete problem which is called “satisfiability problem or SAT”. From SAT a new NP‐complete problem is derived, which is described by a Boolean function called “core function”. In this paper it is proved that the cost of the minimal implementation of core function increases with n exponentially. Since the synthesis of core function is an NP‐complete problem, this result is equivalent to proving that P and NP do not coincide.
On the P vs NP question: a proof on inequality / Meo, ANGELO RAFFAELE. - ELETTRONICO. - (2016), pp. 1-34. [10.6092/polito/porto/2645861]
On the P vs NP question: a proof on inequality
MEO, ANGELO RAFFAELE
2016
Abstract
The analysis discussed in this paper is based on a well‐known NP‐complete problem which is called “satisfiability problem or SAT”. From SAT a new NP‐complete problem is derived, which is described by a Boolean function called “core function”. In this paper it is proved that the cost of the minimal implementation of core function increases with n exponentially. Since the synthesis of core function is an NP‐complete problem, this result is equivalent to proving that P and NP do not coincide.
| File | Dimensione | Formato | |
|---|---|---|---|
|
P-NP15mar2016 (v_9-6).pdf
accesso aperto
Descrizione: Articolo completo analisi problema SAT
Tipologia:
2. Post-print / Author's Accepted Manuscript
Licenza:
Creative commons
Dimensione
383.96 kB
Formato
Adobe PDF
|
383.96 kB | Adobe PDF | Visualizza/Apri |
Pubblicazioni consigliate
I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
https://hdl.handle.net/11583/2645861
Attenzione
Attenzione! I dati visualizzati non sono stati sottoposti a validazione da parte dell'ateneo