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 Tools annual

Global: Zendy Free Plan

Global: Zendy Tools monthly

Global: Zendy Plus monthly

A (1,0)-super solution is a satisfying assignment such that if the value of any one variable is flipped to the opposite value, the new assignment is still a satisfying assignment. Namely, every clause must contain at least two satisfied literals. Because of its robustness, super solutions are concerned in combinatorial optimization problems and decision problems. In this paper, we investigate the existence conditions of the (1,0)-super solution of ( k , s ) -CNF formula, and give a reduction method that transform from k -SAT to (1,0)- ( k + 1 , s ) -SAT if there is a ( k + 1 , s )-CNF formula without a (1,0)-super solution. Here, ( k , s ) -CNF is a subclass of CNF in which each clause has exactly k distinct literals, and each variable occurs at most s times. (1,0)- ( k , s ) -SAT is a problem to decide whether a ( k , s ) -CNF formula has a (1,0)-super solution. We prove that for k &gt; 3 , if there exists a ( k , s ) -CNF formula without a (1,0)-super solution, (1,0)- ( k , s ) -SAT is NP-complete. We show that for k &gt; 3 , there is a critical function φ ( k ) such that every ( k , s ) -CNF formula has a (1,0)-super solution for s ≤ φ ( k ) and (1,0)- ( k , s ) -SAT is NP-complete for s &gt; φ ( k ) . We further show some properties of the critical function φ ( k ) .

(1,0)-Super Solutions of (k,s)-CNF Formula