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/

Zendy Plus

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

Zendy Tools

Zendy Open

We aim at investigating the solvability/insolvability of nondeterministiclogarithmic-space (NL) decision, search, and optimization problemsparameterized by natural size parameters using simultaneously polynomial timeand sub-linear space. We are particularly focused on $\mathrm{2SAT}_3$ -- arestricted variant of the 2CNF Boolean (propositional) formula satisfiabilityproblem in which each variable of a given 2CNF formula appears at most 3 timesin the form of literals -- parameterized by the total number $m_{vbl}(\phi)$ ofvariables of each given Boolean formula $\phi$. We propose a new, practicalworking hypothesis, called the linear space hypothesis (LSH), which assertsthat $(\mathrm{2SAT}_3,m_{vbl})$ cannot be solved in polynomial time using only``sub-linear'' space (i.e., $m_{vbl}(x)^{\varepsilon}\, polylog(|x|)$ space fora constant $\varepsilon\in[0,1)$) on all instances $x$. Immediate consequencesof LSH include $\mathrm{L}l\neq\mathrm{NL}$,$\mathrm{LOGDCFL}\neq\mathrm{LOGCFL}$, and $\mathrm{SC}\neq \mathrm{NSC}$. Forour investigation, we fully utilize a key notion of ``short reductions'', underwhich the class $\mathrm{PsubLIN}$ of all parameterized polynomial-timesub-linear-space solvable problems is indeed closed.

The 2CNF Boolean Formula Satisfiability Problem and the Linear Space Hypothesis