9
views
0
recommends
+1 Recommend
0 collections
0
shares
• Record: found
• Abstract: found
• Article: found
Is Open Access

# Maximizing the Number of Satisfied L-clauses

Preprint

,

Bookmark
There is no author summary for this article yet. Authors can add summaries to their articles on ScienceOpen to make them more accessible to a non-specialist audience.

### Abstract

The $$k$$-SAT problem for \L{}-clausal forms has been found to be NP-complete if $$k\geq 3$$. Similar to Boolean CNF formulas, \L{}-clausal forms are important from a theoretical and practical points of view for their expressive power, easy-hard-easy pattern as well as having a phase transition phenomena. In this paper, we investigate further \L{}-clausal forms in terms of instance generation and maximizing the number of satisfied \L{}-clauses. Firstly, we prove that minimizing the cost of \L{}-clausal forms is NP-complete and present an algorithm for the problem. Secondly, we devise an instance generation model to produce \L{}-clausal forms with different values of $$k$$ and degree of absence of negated terms $$\neg(l_1 \oplus \dots \oplus l_m)$$ (we call $$p$$) in each clause. Finally, we conduct empirical investigation to identify the relationship between the cost and other parameters of the instance generator. One of our findings shows that the cost decreases exponentially as $$p$$ increases, for any clauses to variables ratio. This enables us to generate satisfiable and unsatisfiable instances with the same clauses to variables ratio.

### Most cited references8

• Record: found

### The complexity of theorem-proving procedures

(1971)
Bookmark
• Record: found

### Some simplified NP-complete graph problems

(1976)
Bookmark
• Record: found

### Understanding Random SAT: Beyond the Clauses-to-Variables Ratio

(2004)
Bookmark

### Author and article information

###### Journal
07 June 2018
###### Article
1806.02930