Why Computer Scientists Consult Oracles | Hacker News Reader

Why Computer Scientists Consult Oracles

quantamagazine.org

16 pointsGavCo11 comments

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".

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

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.

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.

I can't speak for anyone else, but this seems to describe how some tech folks use LLMs as sounding boards for their input and thinking things through that they understand, or are understanding and want to get through faster.

This has nothing to do with LLM's. An 'oracle' is a hypothetical construct that is used in proofs. As the article outlines, useful in complexity theory.

I think you misunderstood GP's very concise point. Allow me to expand.

A developer is a Turing Machine that produces low quality code -- and there is a hierarchy of developers (with the mythical 10X on top) that produce a time hierarchy of time classes depending on how fast they are. Depending on the complexity class you're in, the TM may not be able to produce for example a regex, they might be able to do it in exponential time, and the 10X is able to do it in linear time (linear in the number of characters and bugs). LLMs act as oracle that can produce a regex by just asking (an O(1) operation) so that changes the whole time class hierarchy of developers.

So it's the same as in complexity theory, introducing LLM oracles creates analog of the existing complexity hierarchies. This is of particular interest for investors looking to reduce developer cost.

Watching GP and parent discuss oracles.. and missing an actual oracle is so HN.. we use imperfect LLM oracles as sounding boards while we theorize about perfect ones.

Oh, the age we live in - of this new math.

LLMs are math that isn't exact, except when it is more exact, and not always when you need it to be. LLM math can't be too accurate or warm or the math doesn't work as well. Like an O(1) operation that randomly decides to run in O(n!).

Humans, technically are just higher maintenance Turing Machines who incrementally write less buggy code.

LLMs get trained on our obi wan buggy odysseys to help them spit out mindbending new ways of regex-ing something and leap to solutions, and chase shiny new things, however it originated.

This shows us we must not only communicate with LLM oracles and perfect Oracles using natural language programming, but to also use the force, just maybe don't trust it to parse HTML. Maybe it knows why it's so hard with to not be able to "ace" any SWE interview to land a high paying job and keep it for more than 12 months.

It's unfortunate that the names oracle and meta have been assigned to corporations. To appreciate how bad this is, imagine if these other words were used for corporate names: heuristic, estimator, polynomial, exponential, etc.

I like the last one. "Exponential Corporation" has a bit of a ring to it. (I mean, they'd probably just be a consultant shop or something, and fall far short of the promise, but it's still a solid name.)

https://www.smbc-comics.com/comic/citations-needed

Reply on news.ycombinator.com