Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Will a prompt that enables GPT-4 to solve easy Sudoku puzzles be found?

manifold.markets

Post reply on HN
Print view View original

11–20 of 68 posts

Re: Will a prompt that enables GPT-4 to solve easy Sudoku puzzles be found?

#11

Post by AdieuToLogic »

heliophobicdude wrote: post #6

The title is funny to me. We should consider a new computation complexity class for LLMs. Let's call the ones that can be solved with a prompt, Promptable. For the problems that we cannot reliably solve with a single prompt yet, let's call them non-deterministic promptable, or NP. Question is, for most of these hard problems, is there a prompt that can solve them? Better yet, is there a prompt good enough that we col…

> Will we ever know if NP can be reduced to P???

My opinion is that it cannot, due to the unbounded nature of NP problems[0]. Regarding sudoku specifically, the question is a bit more nuanced (as described here[1]).

As for the NP nature of sudoko in its general form, a short but very informative description can be found here[2].

HTH

0 - https://en.wikipedia.org/wiki/NP_(complexity)

1 - https://stackoverflow.com/questions/50703174/is-sudoku-np-co...

2 - http://www.cs.ox.ac.uk/people/paul.goldberg/FCS/sudoku.html

Re: Will a prompt that enables GPT-4 to solve easy Sudoku puzzles be found?

#12

Post by akrolsmir »

Austin from Manifold here - cool to see this trending! I thought the structure of this prediction market was especially cool, as it forms a collaborative, crowdsourced puzzle challenge to generate the perfect prompt.

(I've personally bet yes, but not sure if that prediction is holding up...)

Re: Will a prompt that enables GPT-4 to solve easy Sudoku puzzles be found?

#13

Post by coldtea »

thumbuddy wrote: post #9
earthboundkid wrote: post #8

An LLM is a tool. It is a very versatile tool. It can be used in many situations. It does not therefore follow that it should be used in all situations. Even if you wanted to use an AI to solve sudoku, there is no particular reason to begin with a model trained for language modeling instead of a model better suited to the task.

I don't get it there are so many ways to solve sudokus why does anyone care about this anyways?

Well, it's not really about finding a way to solve sudokus.

Nobody involved in this cares for that as a goal in itself.

It's about the mystery of why an LLM can't do it well.

It's about the challenge of finding a way (prompt) to get it to.

It's about what this reveals about the inner workings and limitations of an LLM.

Re: Will a prompt that enables GPT-4 to solve easy Sudoku puzzles be found?

#14

Post by shawntan »

version_five wrote: post #3

> Easy-rated Sudoku puzzle means a puzzle classified as easy by any reputable Sudoku site or puzzle generator. This market plans to use the LA Times(Sudoku - Free daily Sudoku games from the Los Angeles Times (latimes.com)) for judging, but I maintain the option to use a different Sudoku generator. Is there any theoretical reason why an attention based llm could or couldn't generate an answer to an NP hard problem? A…

I recommend reading the theoretical work on the computational capabilities of Transformers: https://twitter.com/lambdaviking/status/1630581475425828864 References to other work can probably be found in that article.

Shameless plug to my own blogpost about this: https://blog.wtf.sg/posts/2023-02-03-the-new-xor-problem/

TL;DR: The theoretical class of problems that Transformers can solve (without Chain-of-Thought style responses) is fairly limited. Generally, universal approximation proofs rely on infinite precision assumptions, which are not practical in reality. Empirical results also show very limited capabilities when tested on certain formal languages.

In the Sudoku case, the problem-length is limited, so one could conceptually make a large enough model that could memorise all solutions to all possible combinations of permissible sudoku boards, which could then just access and read out the solutions.

Re: Will a prompt that enables GPT-4 to solve easy Sudoku puzzles be found?

#15

Post by epylar »

AdieuToLogic wrote: post #7
version_five wrote: post #3

> Easy-rated Sudoku puzzle means a puzzle classified as easy by any reputable Sudoku site or puzzle generator. This market plans to use the LA Times(Sudoku - Free daily Sudoku games from the Los Angeles Times (latimes.com)) for judging, but I maintain the option to use a different Sudoku generator. Is there any theoretical reason why an attention based llm could or couldn't generate an answer to an NP hard problem? A…

> Is there any theoretical reason why an attention based llm could or couldn't generate an answer to an NP hard problem? Putting aside for the moment that a Large Language Model (LLM) is a predictive statistical model based on and producing from what consisted its training set, answering whether or not any algorithm can solve an NP hard problem first requires a clarification; is a brute force exhaustive search allowe…

LLM's aren't statistical in the sense of memorizing percentages of words that come after other words. They are modeling a very high dimensional function using a neural net. I suppose they're statistical in the sense of learning how to mimic what they've seen, but this includes some very surprising emergent abilities as well.

Re: Will a prompt that enables GPT-4 to solve easy Sudoku puzzles be found?

#16

Post by thumbuddy »

coldtea wrote: post #13
thumbuddy wrote: post #9

Earlier quoted context omitted.

I don't get it there are so many ways to solve sudokus why does anyone care about this anyways?

Well, it's not really about finding a way to solve sudokus. Nobody involved in this cares for that as a goal in itself. It's about the mystery of why an LLM can't do it well. It's about the challenge of finding a way (prompt) to get it to. It's about what this reveals about the inner workings and limitations of an LLM.

So maybe I think about things a little differently, but is there a theoretical reason why we should expect a large language model to be good at sudokus? I remember not long ago they often struggled with adding two numbers

Re: Will a prompt that enables GPT-4 to solve easy Sudoku puzzles be found?

#17

Post by thumbuddy »

jyap wrote: post #10
thumbuddy wrote: post #9

Earlier quoted context omitted.

I don't get it there are so many ways to solve sudokus why does anyone care about this anyways?

It’s just a well known problem case that has a straightforward answer that is easily verifiable. Eg. Can a model play tic-tac-toe or solve chess puzzles

I feel like it's kind of a weird question because if you change the random seed enough times maybe one of them could be good at chess puzzles but suck at being a chat bot, or be good at sudokus but be a horrible pair programmer. I don't know what value a lot of these questions bring once a model hits a trillion parameters of which none or very very few are understood.

Re: Will a prompt that enables GPT-4 to solve easy Sudoku puzzles be found?

#18

Post by joe_the_user »

earthboundkid wrote: post #8

An LLM is a tool. It is a very versatile tool. It can be used in many situations. It does not therefore follow that it should be used in all situations. Even if you wanted to use an AI to solve sudoku, there is no particular reason to begin with a model trained for language modeling instead of a model better suited to the task.

I would, uh, bet that you're right.

But given that there has been a lot of discussion of the possibility that an LLM has "general intelligence", it seems worthwhile to figure out whether the solving of a random problem is possible.

Re: Will a prompt that enables GPT-4 to solve easy Sudoku puzzles be found?

#19

Post by janalsncm »

heliophobicdude wrote: post #6

The title is funny to me. We should consider a new computation complexity class for LLMs. Let's call the ones that can be solved with a prompt, Promptable. For the problems that we cannot reliably solve with a single prompt yet, let's call them non-deterministic promptable, or NP. Question is, for most of these hard problems, is there a prompt that can solve them? Better yet, is there a prompt good enough that we col…

Are large language models even Turing complete? Or more specifically, is there something we can say about LLMs as a class with respect to this question?

For any architecture like Vaswani’s GPT or a bigger iteration of it, eventually you run out of attention heads and layers.

If the answer is categorically no, then any sufficiently sophisticated code is not “promotable”. However, I don’t think there’s anything in principle which prevents LLMs from being Turing complete.

Post reply on HN