A Polynomial Decision for 3-SAT
Fuente:
arXiv
Saved in:
| Main Author: | |
|---|---|
| Format: | Preprint |
| Published: |
2022
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866929377441218560 |
|---|---|
| author | Weiss, Angela |
| author_facet | Weiss, Angela |
| contents | We propose a polynomially bounded, in time and space, method to decide whether a given 3-SAT formula is satisfiable or not. The tools we use here are, in fact, very simple. We first decide satisfiability for a particular 3-SAT formula, called pivoted 3-SAT and, after a plain transformation, still keeping the polynomial boundaries, it is shown that 3-SAT formulas can be written as pivoted formulas. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2208_12598 |
| institution | arXiv |
| publishDate | 2022 |
| record_format | arxiv |
| spellingShingle | A Polynomial Decision for 3-SAT Weiss, Angela Data Structures and Algorithms We propose a polynomially bounded, in time and space, method to decide whether a given 3-SAT formula is satisfiable or not. The tools we use here are, in fact, very simple. We first decide satisfiability for a particular 3-SAT formula, called pivoted 3-SAT and, after a plain transformation, still keeping the polynomial boundaries, it is shown that 3-SAT formulas can be written as pivoted formulas. |
| title | A Polynomial Decision for 3-SAT |
| topic | Data Structures and Algorithms |
| url | https://arxiv.org/abs/2208.12598 |