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

We show conditional lower bounds for well-studied #P-hard problems:  (a) The number of satisfying assignments of a 2-CNF formula with n variablescannot be counted in time exp(o(n)), and the same is true for computing thenumber of all independent sets in an n-vertex graph.  (b) The permanent of an n x n matrix with entries 0 and 1 cannot be computedin time exp(o(n)).  (c) The Tutte polynomial of an n-vertex multigraph cannot be computed in timeexp(o(n)) at most evaluation points (x,y) in the case of multigraphs, and itcannot be computed in time exp(o(n/polylog n)) in the case of simple graphs.  Our lower bounds are relative to (variants of) the Exponential TimeHypothesis (ETH), which says that the satisfiability of n-variable 3-CNFformulas cannot be decided in time exp(o(n)). We relax this hypothesis byintroducing its counting version #ETH, namely that the satisfying assignmentscannot be counted in time exp(o(n)). In order to use #ETH for our lower bounds,we transfer the sparsification lemma for d-CNF formulas to the countingsetting.

Exponential Time Complexity of the Permanent and the Tutte Polynomial