Barbosa, Uniform Polynomial Time Bounds, and Promises

Details Barbosa, Uniform Polynomial Time Bounds, and Promises Barbosa, Uniform Polynomial Time Bounds, and Promises

2011-06-06

arxiv.org/abs/1106.1150v1

Computer Science

Computational Complexity

Scientific paper

This note is a commentary on, and critique of, Andre Luiz Barbosa's paper entitled "P != NP Proof." Despite its provocative title, what the paper is seeking to do is not to prove P \neq NP in the standard sense in which that notation is used in the literature. Rather, Barbosa is (and is aware that he is) arguing that a different meaning should be associated with the notation P \neq NP, and he claims to prove the truth of the statement P \neq NP in his quite different sense of that statement. However, we note that (1) the paper fails even on its own terms, as due to a uniformity problem, the paper's proof does not establish, even in its unusual sense of the notation, that P \neq NP; and (2) what the paper means by the claim P \neq NP in fact implies that P \neq NP holds even under the standard meaning that that notation has in the literature (and so it is exceedingly unlikely that Barbosa's proof can be fixed any time soon).

Affiliated with

Also associated with

No associations

Rating

Barbosa, Uniform Polynomial Time Bounds, and Promises 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 Barbosa, Uniform Polynomial Time Bounds, and Promises, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Barbosa, Uniform Polynomial Time Bounds, and Promises will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-390676