Exploring P versus NP
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_ | 1866911810981986304 |
|---|---|
| author | Tang, Jian-Gang |
| author_facet | Tang, Jian-Gang |
| contents | In this article, we discuss the question of whether P equals NP, we do not follow the line of research of many researchers, which is to try to find such a problem Q, and the problem Q belongs to the class of NP-complete, if the problem Q is proved to belong to P, then P and NP are the same, if the problem Q is proved not to belong to P, then P and NP are separated. Our research strategy in this article: Select a problem S of EXP-complete and reduce it to a problem of NP in polynomial time, then S belongs to NP, so EXP = NP, and then from the well-known P neq NP, derive P neq NP. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2209_15410 |
| institution | arXiv |
| publishDate | 2022 |
| record_format | arxiv |
| spellingShingle | Exploring P versus NP Tang, Jian-Gang Computational Complexity Logic 03D15, 68Q15, 03C13, 03B10, 03B05 In this article, we discuss the question of whether P equals NP, we do not follow the line of research of many researchers, which is to try to find such a problem Q, and the problem Q belongs to the class of NP-complete, if the problem Q is proved to belong to P, then P and NP are the same, if the problem Q is proved not to belong to P, then P and NP are separated. Our research strategy in this article: Select a problem S of EXP-complete and reduce it to a problem of NP in polynomial time, then S belongs to NP, so EXP = NP, and then from the well-known P neq NP, derive P neq NP. |
| title | Exploring P versus NP |
| topic | Computational Complexity Logic 03D15, 68Q15, 03C13, 03B10, 03B05 |
| url | https://arxiv.org/abs/2209.15410 |