Hacker News Reader

Comment by kypro | Hacker News Reader

My old AI professor used to say that every problem is a search problem.

The issue is that to find solutions for useful problems you're often searching through highly complex and often infinite solution spaces.

View on HN

I would argue that no actually searchable solution space is really infinite (if only because infinite turing machines can't exist). Finite solution spaces can get more than large enough to be intractable.

What about ℕ? Seems pretty infinite to me, unless with "actually" you mean finite in time and space, which would make your argument a tautology. Or am I missing something?

Almost every "number" "in" N doesn't actually exist. In the search for numbers that exist, we will most likely only ever find a finite set of numbers before the Universe or humanity dies.

("Scare quotes")

Searches happen in finite time an space and, more importantly, systems performing those searches have practical finite limits on parameters that determine size of the space within which that search can take place (such as available memory).

Even within fairly modest finite limits, you can produce a solution space that cannot be significantly searched with the available finite matter and time available in the observable universe.

Thus, the problem with using search isn't that solution spaces can be infinite, but that finite solution spaces can be unimaginably large.

For some problems validation is expensive. Like the particle collider or space telescope, or testing the COVID vaccine. It's actually validation that is the bottleneck in search not ideation.

There's no problem with search. The goal is to search most efficiently.

You mean that by improving search we can solve any problem? What if solution field is infinite, even if we make search algo 10x100 more performant, solution field will still be infinite, no?

Gradient descent is a search. Where does it say the search space has to be small?

Reply on news.ycombinator.com