A Polynomial time Algorithm for 3SAT
Fuente:
arXiv
Saved in:
| Main Author: | |
|---|---|
| Format: | Preprint |
| Published: |
2010
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866911614230331392 |
|---|---|
| author | Du, Lizhi |
| author_facet | Du, Lizhi |
| contents | By creating some new concepts and methods: checking tree, long unit path, direct contradiction unit pair, indirect contradiction unit pair, additional contradiction unit pair, 2-unit layer and 3-unit layer, redundant units, and destroying parallel pairs , we successfully transform solving a 3SAT problem to solving 2SAT problems in polynomial time. Thus we proved that NP=P. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_1004_3702 |
| institution | arXiv |
| publishDate | 2010 |
| record_format | arxiv |
| spellingShingle | A Polynomial time Algorithm for 3SAT Du, Lizhi Data Structures and Algorithms By creating some new concepts and methods: checking tree, long unit path, direct contradiction unit pair, indirect contradiction unit pair, additional contradiction unit pair, 2-unit layer and 3-unit layer, redundant units, and destroying parallel pairs , we successfully transform solving a 3SAT problem to solving 2SAT problems in polynomial time. Thus we proved that NP=P. |
| title | A Polynomial time Algorithm for 3SAT |
| topic | Data Structures and Algorithms |
| url | https://arxiv.org/abs/1004.3702 |