Barbosa, Uniform Polynomial Time Bounds, and Promises
Lane A. Hemaspaandra, Kyle I. Murray, Xiaoqing Tang · arXiv (Cornell University) · 2011
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 eq 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 eq NP, and he claims to prove the truth of the statement P eq 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 eq NP; and (2) what the paper means by the claim P eq NP in fact implies that P eq 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).