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

A weakened version of the Cutting Plane (CP) proof system with a restriction on the degree of falsity of intermediate inequalities was introduced by Goerdt. He proved an exponential lower bound for CP proofs with degree of falsity bounded by n log 2 n+1, where n is the number of variables. Hirsch and Nikolenko strengthened this result by establishing a direct connection between CP and Resolution proofs. This result implies an exponential lower bound on the proof length of the Tseitin-Urquhart tautologies, when the degree of falsity is bounded by cn for some constant c. In this paper we generalize this result for extensions of Lovasz-Schrijver calculi (LS), namely for LS k +CP k proof systems introduced by Grigoriev et al. We show that any LS k +CP k proof with bounded degree of falsity can be transformed into a Res(k) proof. We also prove lower and upper bounds for the new system.

Complexity of Semialgebraic Proofs with Restricted Degree of Falsity12