Considerations on P vs NP
| dc.creator | von Reckow, Alfredo | |
| dc.date | 2007-11-07 | |
| dc.date.accessioned | 2026-07-07T08:41:31Z | |
| dc.date.available | 2026-07-07T08:41:31Z | |
| dc.description | In order to prove that the P of problems is different to the NP class, we consider the satisfability problem of propositional calculus formulae, which is an NP-complete problem. It is shown that, for every search algorithm A, there is a set E(A) containing propositional calculus formulae, each of which requires the algorithm A to take non-polynomial time to find the truth-values of its propositional letters satisfying it. Moreover, E(A)'s size is an exponential function of n, which makes it impossible to detect such formulae in a polynomial time. Hence, the satisfability problem does not have a polynomial complexity | |
| dc.identifier | https://arxiv.org/abs/0711.1177 | |
| dc.identifier | http://arxiv.org/abs/0711.1177 | |
| dc.identifier.uri | http://salesiana.dossiersoluciones.com/handle/123456789/141696 | |
| dc.subject | Computational Complexity | |
| dc.subject | Logic in Computer Science | |
| dc.subject | F.1.3 | |
| dc.title | Considerations on P vs NP | |
| dc.type | text |