An optimization approach for the satisfiability problem
We describe a new approach for solving the satisfiability problem by geometric programming. We focus on the theoretical background and give details of the algorithmic procedure. The algorithm is provably efficient as geometric programming is in essence a polynomial problem. The correctness of the al...
| Main Author: | |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Emerald Publishing
2015-01-01
|
| Series: | Applied Computing and Informatics |
| Subjects: | |
| Online Access: | http://www.sciencedirect.com/science/article/pii/S2210832711000494 |
| _version_ | 1797716506588479488 |
|---|---|
| author | S. Noureddine |
| author_facet | S. Noureddine |
| author_sort | S. Noureddine |
| collection | DOAJ |
| description | We describe a new approach for solving the satisfiability problem by geometric programming. We focus on the theoretical background and give details of the algorithmic procedure. The algorithm is provably efficient as geometric programming is in essence a polynomial problem. The correctness of the algorithm is discussed. The version of the satisfiability problem we study is exact satisfiability with only positive variables, which is known to be NP-complete. |
| first_indexed | 2024-03-12T08:23:25Z |
| format | Article |
| id | doaj.art-252dc081024746399cab58a783fd0112 |
| institution | Directory Open Access Journal |
| issn | 2210-8327 |
| language | English |
| last_indexed | 2024-03-12T08:23:25Z |
| publishDate | 2015-01-01 |
| publisher | Emerald Publishing |
| record_format | Article |
| series | Applied Computing and Informatics |
| spelling | doaj.art-252dc081024746399cab58a783fd01122023-09-02T18:16:35ZengEmerald PublishingApplied Computing and Informatics2210-83272015-01-01111475910.1016/j.aci.2011.11.002An optimization approach for the satisfiability problemS. NoureddineWe describe a new approach for solving the satisfiability problem by geometric programming. We focus on the theoretical background and give details of the algorithmic procedure. The algorithm is provably efficient as geometric programming is in essence a polynomial problem. The correctness of the algorithm is discussed. The version of the satisfiability problem we study is exact satisfiability with only positive variables, which is known to be NP-complete.http://www.sciencedirect.com/science/article/pii/S2210832711000494SatisfiabilityNP-complete problemOptimizationGeometric programming |
| spellingShingle | S. Noureddine An optimization approach for the satisfiability problem Applied Computing and Informatics Satisfiability NP-complete problem Optimization Geometric programming |
| title | An optimization approach for the satisfiability problem |
| title_full | An optimization approach for the satisfiability problem |
| title_fullStr | An optimization approach for the satisfiability problem |
| title_full_unstemmed | An optimization approach for the satisfiability problem |
| title_short | An optimization approach for the satisfiability problem |
| title_sort | optimization approach for the satisfiability problem |
| topic | Satisfiability NP-complete problem Optimization Geometric programming |
| url | http://www.sciencedirect.com/science/article/pii/S2210832711000494 |
| work_keys_str_mv | AT snoureddine anoptimizationapproachforthesatisfiabilityproblem AT snoureddine optimizationapproachforthesatisfiabilityproblem |