Return to Answer

Apparently, we would have gotten at least half of the BGS result without any of the three named authors and also without any of the 4 people they credit, all we needed was Dekhtiar. 😊

The Annals of the History of Computing (1984) has a historical account by Trakhtenbrot of the proof by Dekhtiar (1969) that we can have $P^A\ne NP^A$.

Trakhtenbrot also explains that the $P^A\ne NP^A (\exists A)$ question was for him the main question they had been investigating, and was not viewed as a relativization of something else.

• $P^A\ne NP^A (\exists A)$ says that there is no way to short-circuit an exhaustive search through an external database, whereas
• $P\ne NP$ says that there is no way to short-circuit an exhaustive search through a mathematical space defined by the input string.

Apparently, we would have gotten at least half of the BGS result without any of the three named authors and also without any of the 4 people they credit, all we needed was Dekhtiar. 😊

The Annals of the History of Computing (1984) has a historical account by Trakhtenbrot of the proof by Dekhtiar (1969) that we can have $P^A\ne NP^A$.

Trakhtenbrot also explains that the $P^A\ne NP^A (\exists A)$ question was for him the main question they had been investigating, and was not viewed as a relativization of something else.

• $P\ne NP$ says that there is no way to short-circuit an exhaustive search through a mathematical space defined by the input string;
• $P^A\ne NP^A (\exists A)$ says that there is no way to short-circuit an exhaustive search through a mathematical space defined by a combination of (i) the input string and (ii) an external database.

Apparently, we would have gotten at least half of the BGS result without any of the three named authors and also without any of the 4 people they credit, all we needed was Dekhtiar. 😊

The Annals of the History of Computing (1984) has a historical account by Trakhtenbrot of the proof by Dekhtiar (1969) that we can have $P^A\ne NP^A$.

Trakhtenbrot also explains that the $P^A\ne NP^A (\exists A)$ question was for him more interesting than $P\ne NP$ itself, so he considered the subject matter settled at the time.

Apparently, we would have gotten at least half of the BGS result without any of the three named authors and also without any of the 4 people they credit, all we needed was Dekhtiar. 😊

The Annals of the History of Computing (1984) has a historical account by Trakhtenbrot of the proof by Dekhtiar (1969) that we can have $P^A\ne NP^A$.

Trakhtenbrot also explains that the $P^A\ne NP^A (\exists A)$ question was for him the main question they had been investigating, and was not viewed as a relativization of something else.

• $P^A\ne NP^A (\exists A)$ says that there is no way to short-circuit an exhaustive search through an external database, whereas
• $P\ne NP$ says that there is no way to short-circuit an exhaustive search through a mathematical space defined by the input string.

Apparently, we would have gotten at least half of the BGS result without any of the three named authors and also without any of the 4 people they credit, all we needed was Dekhtiar. 😊

The Annals of the History of Computing (1984) has a historical account by Trakhtenbrot of the proof by Dekhtiar (1969) that we can have $P^A\ne NP^A$.

Apparently, we would have gotten at least half of the BGS result without any of the three named authors and also without any of the 4 people they credit, all we needed was Dekhtiar. 😊

The Annals of the History of Computing (1984) has a historical account by Trakhtenbrot of the proof by Dekhtiar (1969) that we can have $P^A\ne NP^A$.

Trakhtenbrot also explains that the $P^A\ne NP^A (\exists A)$ question was for him more interesting than $P\ne NP$ itself, so he considered the subject matter settled at the time.