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 Plus annual

Presents the access of premium content as premium feature

Premium Content

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 Plus monthly

Global: Zendy Tools annual

Global: Zendy Tools monthly

Global: Zendy Free Plan

It is well known that there is a sharp density threshold for a random $r$-SATformula to be satisfiable, and a similar, smaller, threshold for it to besatisfied by the pure literal rule. Also, above the satisfiability threshold,where a random formula is with high probability (whp) unsatisfiable, theunsatisfiability is whp due to a large "minimal unsatisfiable subformula"(MUF).  By contrast, we show that for the (rare) unsatisfiable formulae below thepure literal threshold, the unsatisfiability is whp due to a unique MUF withsmallest possible "excess", failing this whp due to a unique MUF with the nextlarger excess, and so forth. In the same regime, we give a precise asymptoticexpansion for the probability that a formula is unsatisfiable, and efficientalgorithms for satisfying a formula or proving its unsatisfiability. It remainsopen what happens between the pure literal threshold and the satisfiabilitythreshold. We prove analogous results for the $k$-core and $k$-colorabilitythresholds for a random graph, or more generally a random $r$-uniformhypergraph.

Structure of random r-SAT below the pure literal threshold