logoalt Hacker News

406380581today at 1:30 PM2 repliesview on HN

The lower bound had already been established in prior work: https://zenodo.org/records/18568303


Replies

bsubstoday at 6:25 PM

I'm one of the authors of the arXiv paper. Thanks for bringing this to our attention! We were fully unaware of this repository, and it unfortunately did not come up during our literature search. Our approaches to the lower bound are pretty similar, although some technical differences make ours more efficient. For example, to show that there is no counterexample of size 10, we generate a formula with ~50k variables and ~2.7M clauses, which takes about 85 seconds to solve with Kissat. The encoder from this repository generates a formula with ~2k variables and ~33M clauses, which takes about 50 minutes to solve. We have sent an email to the authors of the Zenodo artifact to decide how to proceed!

MableCookietoday at 3:50 PM

I think you are right, it's weird that the paper doesn't mention it