23
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
      ,

      Read this article at

      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.

          Related collections

          Most cited references8

          • Record: found
          • Abstract: not found
          • Conference Proceedings: not found

          The complexity of theorem-proving procedures

            Bookmark
            • Record: found
            • Abstract: not found
            • Article: not found

            Some simplified NP-complete graph problems

              Bookmark
              • Record: found
              • Abstract: not found
              • Book Chapter: not found

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

                Bookmark

                Author and article information

                Journal
                07 June 2018
                Article
                1806.02930
                8a30aaf9-f9eb-4f92-a1a7-a773c160522a

                http://arxiv.org/licenses/nonexclusive-distrib/1.0/

                History
                Custom metadata
                8 pages, 4 figures
                cs.LO cs.CC math.LO

                Theoretical computer science,Logic & Foundation
                Theoretical computer science, Logic & Foundation

                Comments

                Comment on this article