Skip to main content
Improved writing
Source Link
Joel David Hamkins
  • 236.3k
  • 44
  • 777
  • 1.4k

The others have pointed out the flaw in your suggested argument, but let me discuss something from the first part of your post.

The conclusion of the Baker-Gill-Solovay relativization result (that there are oracles $A$ and $B$ for which $P^A=NP^A$ and $P^B\neq NP^B$) isn't just that "we can't solve the problem of NP=P by relativization," as you say, but rather something more profound: the conclusion is that we cannot solve the NP=P problem by any method that admits of relativization. This is an enormous class of methods, which includes all of the standard powerful methods of computability theory. The reason is that if we could prove $P=NP$ or $P\neq NP$ using methods that can accommodate oracles, then we would immediately deduce the corresponding equality or inequality for all oracles, in contradiction to the Baker-Gill-Solovay result.

The significance of this is therefore that since all the standard methods do admit relativaizationrelativization, we will not be able to settle P versus NP using only those methods; we must be more imaginative and subtle. Any purported proof answering P versus NP must make use of proof methods that do not relativize to oracles.

TheThat is, the point isn't that the theorem rules out the one method of relativization as a method of solving P versus NP, but rather that it rules out any methodall methods that admits ofaccommodate relativization. Since this includes most of our methods, it is a serious obstacle.

The others have pointed out the flaw in your suggested argument, but let me discuss something from the first part of your post.

The conclusion of the Baker-Gill-Solovay relativization result (that there are oracles $A$ and $B$ for which $P^A=NP^A$ and $P^B\neq NP^B$) isn't just that "we can't solve the problem of NP=P by relativization," as you say, but rather something more profound: the conclusion is that we cannot solve the NP=P problem by any method that admits of relativization. This is an enormous class of methods, which includes all of the standard powerful methods of computability theory. The reason is that if we could prove $P=NP$ or $P\neq NP$ using methods that can accommodate oracles, then we would immediately deduce the corresponding equality or inequality for all oracles, in contradiction to the Baker-Gill-Solovay result.

The significance of this is therefore that since all the standard methods do admit relativaization, we will not be able to settle P versus NP using only those methods; we must be more imaginative and subtle. Any purported proof answering P versus NP must make use of proof methods that do not relativize to oracles.

The point isn't that the theorem rules out relativization as a method of solving P versus NP, but rather that it rules out any method that admits of relativization. Since this includes most of our methods, it is a serious obstacle.

The others have pointed out the flaw in your suggested argument, but let me discuss something from the first part of your post.

The conclusion of the Baker-Gill-Solovay relativization result (that there are oracles $A$ and $B$ for which $P^A=NP^A$ and $P^B\neq NP^B$) isn't that "we can't solve the problem of NP=P by relativization," as you say, but rather something more profound: the conclusion is that we cannot solve the NP=P problem by any method that admits of relativization. This is an enormous class of methods, which includes all of the standard powerful methods of computability theory. The reason is that if we could prove $P=NP$ or $P\neq NP$ using methods that can accommodate oracles, then we would immediately deduce the corresponding equality or inequality for all oracles, in contradiction to the Baker-Gill-Solovay result.

The significance of this is that since all the standard methods do admit relativization, we will not be able to settle P versus NP using only those methods; we must be more imaginative and subtle.

That is, the point isn't that the theorem rules out the one method of relativization as a method of solving P versus NP, but rather that it rules out all methods that accommodate relativization. Since this includes most of our methods, it is a serious obstacle.

Source Link
Joel David Hamkins
  • 236.3k
  • 44
  • 777
  • 1.4k

The others have pointed out the flaw in your suggested argument, but let me discuss something from the first part of your post.

The conclusion of the Baker-Gill-Solovay relativization result (that there are oracles $A$ and $B$ for which $P^A=NP^A$ and $P^B\neq NP^B$) isn't just that "we can't solve the problem of NP=P by relativization," as you say, but rather something more profound: the conclusion is that we cannot solve the NP=P problem by any method that admits of relativization. This is an enormous class of methods, which includes all of the standard powerful methods of computability theory. The reason is that if we could prove $P=NP$ or $P\neq NP$ using methods that can accommodate oracles, then we would immediately deduce the corresponding equality or inequality for all oracles, in contradiction to the Baker-Gill-Solovay result.

The significance of this is therefore that since all the standard methods do admit relativaization, we will not be able to settle P versus NP using only those methods; we must be more imaginative and subtle. Any purported proof answering P versus NP must make use of proof methods that do not relativize to oracles.

The point isn't that the theorem rules out relativization as a method of solving P versus NP, but rather that it rules out any method that admits of relativization. Since this includes most of our methods, it is a serious obstacle.