문제의 λ‚œμ΄λ„λ₯Ό μ΅œμ†Œ μ΄λ™νšŸμˆ˜λ‘œ μ •μ˜ν•œ 것에도 λ¬Έμ œκ°€ μžˆλ‹€λŠ” 지적이 μžˆμŠ΅λ‹ˆλ‹€. ν•˜λ…Έμ΄μ˜ 탑은 μ •ν•΄μ§„ 길만 따라가면 ν’€λ¦¬λŠ” λ¬Έμ œμ§€λ§Œ, κ°• κ±΄λ„ˆκΈ° λ“± λ‹€λ₯Έ λ¬Έμ œλŠ” 맀번 이동할 λ•Œλ§ˆλ‹€ μ—¬λŸ¬ κ°€μ§€ 선택지가 λ‚˜μ˜€κΈ° λ•Œλ¬Έμ— λͺ¨λ“  경우의 수λ₯Ό 확인해봐야 ν•˜λŠ”λ° 원본 λ…Όλ¬Έμ—μ„œλŠ” 문제의 닡을 νƒμƒ‰ν•˜λŠ” λ‚œμ΄λ„λ₯Ό κ³ λ €ν•˜μ§€ μ•Šκ³  μžˆμŠ΅λ‹ˆλ‹€.

같은 λ…Όλ¬Έ 발췌:

6 Reevaluating Complexity Claims

The authors use "compositional depth" (minimum moves) as their complexity metric, but this conflates mechanical execution with problem-solving difficulty:

Table 1: Problem complexity is not determined by solution length alone

Tower of Hanoi
* Solution Length: 2^N - 1
* Branching Factor: 1
* Search Required: No

River Crossing
* Solution Length: ~4N
* Branching Factor: >4
* Search Required: Yes (NP-hard)

Blocks World
* Solution Length: ~2N
* Branching Factor: O(N^2)
* Search Required: Yes (PSPACE)

Tower of Hanoi, despite requiring exponentially many moves, has a trivial O(1) decision process per move. River Crossing, with far fewer moves, requires complex constraint satisfaction and search. This explains why models might execute 100+ Hanoi moves while failing on 5-move River Crossing problems.
0

If you have a fediverse account, you can quote this note from your own instance. Search https://bsky.brid.gy/convert/ap/at://did:plc:ppk763j7o2wkinvzuqx4orrb/app.bsky.feed.post/3lrpqr6rn7c24 on your instance and quote it. (Note that quoting is not supported in Mastodon.)