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 introduce a concept of efficiency for which we can prove that it appliesto all paddable languages, but still does not conflict with potential worstcase intractability. Note that the family of paddable languages apparentlyincludes all known natural NP-complete problems. We call our concept RoughlyPolynomial Time (RoughP). A language $L,$ over an at least 2-symbol alphabet,is in RoughP, if the following hold: (1) there exists a bijective encoding$\alpha$ of strings, such that both $\alpha$ and its inverse are computable inpolynomial time; (2) there is a polynomial time algorithm $\cal A$, which is anerrorless heuristic for $L,$ with exponentially vanishing failure rate relativeto the $\alpha$-spheres $S^{(\alpha)}_n=\{\alpha(x)\,|\;\, |x|=n\}$. It means,$\cal A$ always correctly decides whether $x\in L$ or $x\notin L$, whenever itoutputs a decision. For some inputs, however, it may not output a decision,rather it may return a special sign, meaning "don't know." But the latter canhappen only on an exponentially small fraction of each $\alpha$-sphere. Weprove that RoughP contains all paddable languages. This may contribute to theexplanation of the often observed gap between practical algorithm performanceand theoretical worst case analysis for hard problems. Furthermore, the proofalso provides a general method to construct the desired encoding and theerrorless heuristic. Additionally, we also show how to use it for efficientlygenerating large, random, guaranteed positive and negative test instances forany paddable language, including all known natural NP-complete problems. Infact, it appears that every practical decision task (whether in NP or not) canbe represented by paddable languages, and, therefore, our RoughP frameworkapplies to all of them. We also explore some connections between RoughP andother complexity classes.

Roughly Polynomial Time: A Concept of Tractability Covering All Known Natural NP-complete Problems