Hmmm... 🤔
"In this work, we prove the NP-completeness of two variants of tokenisation, defined as the problem of compressing a dataset to at most δ symbols by either finding a vocabulary directly (direct tokenisation), or selecting a sequence of merge operations (bottom-up tokenisation)."
Tokenisation is NP-Complete [PDF] https://arxiv.org/pdf/2412.15210 #compsci #paper
Vladimir Savić
npub16g…45mgn
2024-12-23 19:03:17 UTC
Author Public Key
npub16gwdrptcxzppxyx4vmzza3l4kl9xg8qxs29y64w0g6wurqnms80sv45mgnSeen on
wss://relay.ditto.pubPublished at
2024-12-23 19:03:17 UTCEvent JSON
{
"id": "3c07df0cf69f5b691d9dfc8a17a99a8b9dc25364572f29321d6b035c29efd157",
"pubkey": "d21cd1857830821310d566c42ec7f5b7ca641c06828a4d55cf469dc1827b81df",
"created_at": 1734980597,
"kind": 1,
"tags": [
[
"t",
"compsci"
],
[
"t",
"paper"
],
[
"proxy",
"https://mastodon.social/users/firusvg/statuses/113703688421350353",
"activitypub"
]
],
"content": "Hmmm... 🤔\n\n\"In this work, we prove the NP-completeness of two variants of tokenisation, defined as the problem of compressing a dataset to at most δ symbols by either finding a vocabulary directly (direct tokenisation), or selecting a sequence of merge operations (bottom-up tokenisation).\" \n\nTokenisation is NP-Complete [PDF] https://arxiv.org/pdf/2412.15210 #compsci #paper",
"sig": "3dd98eefbb598718f7f0dd588ec443a6534e3e1080bc64e1e41657e191b1895361e0536e64eb9b9f3acf63e926fc42ee696601f04cf94677bdbc71cd4a6cf680"
}