{
  "$type": "site.standard.document",
  "bskyPostRef": {
    "cid": "bafyreiajn3uccbumdzmlbxeyvnfpgwnmzfjy2juvfw2ne2srr6fecc4yxu",
    "uri": "at://did:plc:3fychdutjjusoqeq24ljch6q/app.bsky.feed.post/3mnz62t7eyaw2"
  },
  "coverImage": {
    "$type": "blob",
    "ref": {
      "$link": "bafkreiflo6xt7is6b2iafwghkjahlgggocme5jwjsbeuqqwcywuvjhmszm"
    },
    "mimeType": "image/png",
    "size": 24783
  },
  "path": "/abs/2606.12130v1",
  "publishedAt": "2026-06-11T00:00:00.000Z",
  "site": "https://arxiv.org",
  "tags": [
    "Yichuan Cao",
    "Ruichen Qiu",
    "Qiao-Long Huang",
    "Ruyong Feng",
    "Xiao-Shan Gao"
  ],
  "textContent": "**Authors:** Yichuan Cao, Ruichen Qiu, Qiao-Long Huang, Ruyong Feng, Xiao-Shan Gao\n\nIn this paper, we show that deciding whether a sparse polynomial does not divide another sparse polynomial exactly over finite fields is NP-hard under BPP many-one reductions. Equivalently, the sparse polynomial divisibility test over finite fields is CoNP-hard. This resolves the long-standing open problem concerning the computational complexity of the divisibility test for sparse polynomials in the setting of finite fields.",
  "title": "Sparse Polynomial Divisibility Test over Finite Field is CoNP-hard"
}