| dc.contributor.author | Maknickas, Algirdas | |
| dc.date.accessioned | 2023-09-18T19:59:03Z | |
| dc.date.available | 2023-09-18T19:59:03Z | |
| dc.date.issued | 2014 | |
| dc.identifier.other | (BIS)VGT02-000027396 | |
| dc.identifier.uri | https://etalpykla.vilniustech.lt/handle/123456789/145531 | |
| dc.description.abstract | It was investigated the Boolean satisfiability (SAT) problem defined as follows: given a Boolean formula, check whether an assignment of Boolean values to the propositional variables in the formula exists, such that the formula evaluates to true. If such an assignment exists, the formula is said to be satisfiable; otherwise, it is unsatisfiable. With using of analytical expressions of multi-valued logic 2SAT boolean satisfiability was formulated as linear programming optimization problem. The same linear programming formulation was extended to find 3SAT and kSAT boolean satisfiability for k greater than 3. So, using new analytic multi-valued logic expressions and linear programming formulation of boolean satisfiability proposition that kSAT is in P and could be solved in linear time was proved. | eng |
| dc.format | PDF | |
| dc.format.extent | p. 305-321 | |
| dc.format.medium | tekstas / txt | |
| dc.language.iso | eng | |
| dc.relation.isreferencedby | SpringerLink | |
| dc.source.uri | http://link.springer.com/chapter/10.1007/978-94-007-7684-5_22 | |
| dc.subject | IK01 - Informacinės technologijos, ontologinės ir telematikos sistemos / Information technologies, ontological and telematic systems | |
| dc.title | Linear programming formulation of Boolean satisfiability problem | |
| dc.type | Straipsnis kitoje DB / Article in other DB | |
| dcterms.references | 14 | |
| dc.type.pubtype | S3 - Straipsnis kitoje DB / Article in other DB | |
| dc.contributor.institution | Vilniaus Gedimino technikos universitetas | |
| dc.contributor.faculty | Mechanikos fakultetas / Faculty of Mechanics | |
| dc.subject.researchfield | N 009 - Informatika / Computer science | |
| dc.subject.ltspecializations | L106 - Transportas, logistika ir informacinės ir ryšių technologijos (IRT) / Transport, logistic and information and communication technologies | |
| dc.subject.en | Boolean satisfiability | |
| dc.subject.en | Conjunctive normal form | |
| dc.subject.en | Convex function | |
| dc.subject.en | Linear programming | |
| dc.subject.en | Multi-valued logic | |
| dc.subject.en | NP problem | |
| dc.subject.en | Time complexity | |
| dcterms.sourcetitle | Transactions on Engineering Technologies : International MultiConference of Engineers and Computer Scientists 2013 | |
| dc.publisher.name | Springer | |
| dc.publisher.city | Amsterdam | |
| dc.identifier.doi | 10.1007/978-94-007-7684-5_22 | |
| dc.identifier.elaba | 4049143 | |
