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

31–40 of 68 posts

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

#31

Post by ComplexSystems »

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…

From what I can tell, experts currently project the problem "TURN HUMANS TO PAPERCLIPS" is in complexity class "Promptable," but that the Boolean Satisfiability problem is not in "Promptable."

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

#32

Post by gwern »

shawntan wrote: post #14
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…

> The theoretical class of problems that Transformers can solve (without Chain-of-Thought style responses) is fairly limited.

Which is irrelevant because how would a Transformer emit a complete Sudoku solution in a single forward-pass/token in the first place?

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

#33

Post by CydeWeys »

solomatov wrote: post #30
bippihippi1 wrote: post #26

Earlier quoted context omitted.

attention is turing complete https://news.ycombinator.com/item?id=36332033 I'd guess it's not as efficient as a native algorithm i many cases though

It's not realistically Turing complete. It assumes infinite precision.

Right but a Turing computer assumes infinite storage space which is itself impossible. You cannot have infinite precision without infinite storage, and all real computers that we colloquially say are Turing complete have finite everything.

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

#35

Post by eschaton »

swayvil wrote: post #34

Can we use this technology to find a recognizable pattern in any complex blob of data? Is that how this works? How about, "Given 100000 readings from a person's body/brain, determine whether they are lying". Can we do that?

I don’t understand how so many people on Hacker News engage in this line of questioning.

If by “this technology” you mean “large neural networks” the answer is yes, and we’ve been doing so for several decades now. That’s very specifically what they’re good at.

If you mean “LLMs like ChatGPT” specifically, then no, they’re extremely large neural networks trained on very specific data sets. To perform a different recognition task, you train with different data sets.

Where does this idea that ChatGPT and friends are general-purpose come from?

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

#36

Post by ineedasername »

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…

Or prompt(n) time, where n = the known minimum # of prompts required to solve a given class of problems.

From there we can define various classes of problems:

1) those with an absolute floor minimum # of required prompts

2) those with a known ceiling

Etc.

This should be combined with traditional Big-O notation to provide a more specific classification, e.g. a constant-time complexity task with a known ceiling of two prompts would be prompt(2)-O(1)

A problem known to, in some specific cases but not all, be solvable with some minimum number of prompts with no ceiling known might be Prompt(n(np)) where n = minimum prompts known to solve at least some problems in that class.

Classifications would be applied to specific systems but the best performing system would set the general classification for a problem. So the general classification for a problem might be prompt(1(5)) to denote a min 1 max 5 prompts required based on the best performance seen to date, a specific system might only rate a prompt(3(np)) classification.

I’m overthink this but I think I like it.

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

#37

Post by famouswaffles »

eschaton wrote: post #35
swayvil wrote: post #34

Can we use this technology to find a recognizable pattern in any complex blob of data? Is that how this works? How about, "Given 100000 readings from a person's body/brain, determine whether they are lying". Can we do that?

I don’t understand how so many people on Hacker News engage in this line of questioning. If by “this technology” you mean “large neural networks” the answer is yes, and we’ve been doing so for several decades now. That’s very specifically what they’re good at. If you mean “LLMs like ChatGPT” specifically, then no, they’re extremely large neural networks trained on very specific data sets . To perform a different reco…

>Where does this idea that ChatGPT and friends are general-purpose come from?

Maybe reality?

https://general-pattern-machines.github.io/

Large Language Models are as general purpose as they come especially for Machine Learning. They generalize to any kind of pattern, linguistic or not.

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

#38

Post by famouswaffles »

swayvil wrote: post #34

Can we use this technology to find a recognizable pattern in any complex blob of data? Is that how this works? How about, "Given 100000 readings from a person's body/brain, determine whether they are lying". Can we do that?

>Can we use this technology to find a recognizable pattern in any complex blob of data? Is that how this works?

Possibly in general. https://general-pattern-machines.github.io/

As for your example, I don't think so.

Post reply on HN