3 ms·

After reading the article I still have no idea what that "oracle" is thus I cannot assess the "why" consulting it. Even the article doesn't go into much depth i

by soco 2y ago

After reading the article I still have no idea what that "oracle" is thus I cannot assess the "why" consulting it. Even the article doesn't go into much depth into the "why" rather into the "how".

GavCo 2y ago
Oracles are hypothetical constructs so it's a bit difficult to define concretely. They are used in thought experiments within mathematical proofs. From what I remember from my Comp Sci studies, they were sometimes used in negative proofs — you imagine you had an oracle who could magically tell you the correct answer, and this eventually leads to a logical contradiction
Sharlin 2y ago
This was a bit disappointing article by Quanta standards, pretty much just felt like the introductory part of a longer article. The "why" is that if we assume, as a thought experiment, that we have a magic black box that always gives the correct answer to some question that we otherwise don't (or can't) know the answer to, it can help us come up with and prove results about computational complexity that apply to the "real", oracle-less world too.
woolion 2y ago
An oracle is basically any device/API that you can plug into a Turing Machine to give you the answer to some problem. You can have an oracle to answer the question "what is the optimal path that visits all these points" (an NP-complete problem) or even "does this program have an input that makes it loop infinitely" (an undecidable problem). The point is simply to explore the consequences regarding computability and complexity if Turing machines can access such oracles. By definition, a machine with access to the first type of oracle gives you a O(1) solution to any NP-complete problem. But how does it react on more complicated problems, such as NEXP-TIME (non-deterministic exponential time) or PSPACE (polynomial space)? Does it even help or not? The idea is to test different class of problems with different classes of oracles to create analogs of the complexity hierarchy. The hope is that the relationships between these analogs provide a deeper understanding of the standard hierarchy.

by soco 2y ago

After reading the article I still have no idea what that "oracle" is thus I cannot assess the "why" consulting it. Even the article doesn't go into much depth into the "why" rather into the "how".

GavCo 2y ago

Oracles are hypothetical constructs so it's a bit difficult to define concretely. They are used in thought experiments within mathematical proofs. From what I remember from my Comp Sci studies, they were sometimes used in negative proofs — you imagine you had an oracle who could magically tell you the correct answer, and this eventually leads to a logical contradiction

Sharlin 2y ago

This was a bit disappointing article by Quanta standards, pretty much just felt like the introductory part of a longer article. The "why" is that if we assume, as a thought experiment, that we have a magic black box that always gives the correct answer to some question that we otherwise don't (or can't) know the answer to, it can help us come up with and prove results about computational complexity that apply to the "real", oracle-less world too.

woolion 2y ago

An oracle is basically any device/API that you can plug into a Turing Machine to give you the answer to some problem. You can have an oracle to answer the question "what is the optimal path that visits all these points" (an NP-complete problem) or even "does this program have an input that makes it loop infinitely" (an undecidable problem). The point is simply to explore the consequences regarding computability and complexity if Turing machines can access such oracles. By definition, a machine with access to the first type of oracle gives you a O(1) solution to any NP-complete problem. But how does it react on more complicated problems, such as NEXP-TIME (non-deterministic exponential time) or PSPACE (polynomial space)? Does it even help or not? The idea is to test different class of problems with different classes of oracles to create analogs of the complexity hierarchy. The hope is that the relationships between these analogs provide a deeper understanding of the standard hierarchy.