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

In the nineties Immerman and Medina initiated the search for syn- tactictools to prove NP-completeness. In their work, amongst several results, theyconjecture that the NP-completeness of a problem defined by the conjunction ofa sentence in Existential Second Order Logic with a First Order sentence,necessarily imply the NP-completeness of the problem defined by the ExistentialSecond Order sentence alone. This is interesting because if true it wouldjustify the restriction heuristic pro- posed in Garey and Johnson in hisclassical book on NP completeness, which roughly says that in some cases onecan prove NP- complete a problem A by proving NP-complete a problem B containedin A. Borges and Bonet extend some results from Immerman and Medina and theyalso prove for a host of complexity classes that the Immerman- Medinaconjecture is true when the First Order sentence in the conjunc- tion isuniversal. Our work extends that result to the Second Level of thePolynomial-Time Hierarchy.

A syntactic tool for proving hardness in the Second Level of the Polynomial-Time Hierarchy