Considerations on P vs NP

Details Considerations on P vs NP Considerations on P vs NP

2007-11-07

arxiv.org/abs/0711.1177v1

Computer Science

Computational Complexity

Scientific paper

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

Affiliated with

Also associated with

No associations

Rating

Considerations on P vs NP does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Considerations on P vs NP, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Considerations on P vs NP will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-377305