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

We study random instances of the weighted $d$-CNF satisfiability problem(WEIGHTED $d$-SAT), a generic W[1]-complete problem. A random instance of theproblem consists of a fixed parameter $k$ and a random $d$-CNF formula$\weicnf{n}{p}{k, d}$ generated as follows: for each subset of $d$ variablesand with probability $p$, a clause over the $d$ variables is selected uniformlyat random from among the $2^d - 1$ clauses that contain at least one negatedliterals.  We show that random instances of WEIGHTED $d$-SAT can be solved in $O(k^2n +n^{O(1)})$-time with high probability, indicating that typical instances ofWEIGHTED $d$-SAT under this instance distribution are fixed-parametertractable. The result also hold for random instances from the model$\weicnf{n}{p}{k,d}(d')$ where clauses containing less than $d' (1 < d' < d)$negated literals are forbidden, and for random instances of the renormalized(miniaturized) version of WEIGHTED $d$-SAT in certain range of the randommodel's parameter $p(n)$. This, together with our previous results on thethreshold behavior and the resolution complexity of unsatisfiable instances of$\weicnf{n}{p}{k, d}$, provides an almost complete characterization of thetypical-case behavior of random instances of WEIGHTED $d$-SAT.

A Fixed-Parameter Algorithm for Random Instances of Weighted d-CNF Satisfiability