Hackers' Pub

Hackers’ Pub

Syntax	Description	Examples
`"` keyword `"`	Finds the string within quotes, including spaces. Case-insensitive. (Escape quotes inside with `\"`)	`"Hackers' Pub"`
`from:` handle	Finds content written by the specified user.	`from:hongminhee` `from:hongminhee@hollo.social`
`lang:` ISO 639-1	Finds content written in the specified language.	`lang:en`
`#` tag	Finds content with the specified tag. Case-insensitive.	`#HackersPub`
condition condition	Finds content that satisfies both conditions on either side of the space (logical AND).	`"Hackers' Pub" lang:en`
condition `OR` condition	Finds content that satisfies at least one of the conditions on either side of the OR operator (logical OR).	`#HackersPub OR "Hackers' Pub" lang:en`
`(` condition `)`	Combines the operators within the parentheses first.	`(#HackersPub OR "Hackers' Pub" OR "Hackers Pub") lang:en`

잇창명 EatChangmyeong💕 @eatch.dev@bsky.brid.gy

6/16/2025, 10:15:48 AM

Public

문제의 난이도를 최소 이동횟수로 정의한 것에도 문제가 있다는 지적이 있습니다. 하노이의 탑은 정해진 길만 따라가면 풀리는 문제지만, 강 건너기 등 다른 문제는 매번 이동할 때마다 여러 가지 선택지가 나오기 때문에 모든 경우의 수를 확인해봐야 하는데 원본 논문에서는 문제의 답을 탐색하는 난이도를 고려하지 않고 있습니다.

같은 논문 발췌:

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.

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