English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Tools annual

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Tools monthly

Global: Zendy Plus monthly

Presents the access of premium content as premium feature

Premium Content

Global: Zendy Plus annual

Global: Zendy Free Plan

In this paper, we take a closer look at the claims made by Xu and Zhou intheir paper "SAT Requires Exhaustive Search" [XZ23], which claims to provide alower bound on the complexity of the so-called Model RB. Xu and Zhou concludethat their result implies a separation between P and NP, since the lower boundpurportedly proves that the Strong Exponential Time Hypothesis (SETH) is true.In examining Xu and Zhou's arguments, we find a flaw in their main theorems.The authors assume that an algorithm for Model RB must have a certain structurethat can leverage downward self-reducibility, and argue that such an algorithmcannot run in polynomial time. We argue that this structure is not guaranteedto exist and thus their paper neither proves SETH to be true nor proves P$\neq$ NP.

Evaluating the Claims of "SAT Requires Exhaustive Search"