Computer-Aided Verification of P/NP Proofs: A Survey and Discussion
We survey a collection of proofs towards equality, inequality, or independence of the relation of P to NP. Since the problem has attracted much attention from experts, amateurs, and in-betweens, this work is intended as a pointer into directions to enable a “self-assessment” of...
| Main Authors: | , , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
IEEE
2024-01-01
|
| Series: | IEEE Access |
| Subjects: | |
| Online Access: | https://ieeexplore.ieee.org/document/10403917/ |
| _version_ | 1797339242835214336 |
|---|---|
| author | Stefan Rass Max-Julian Jakobitsch Stefan Haan Moritz Hiebler |
| author_facet | Stefan Rass Max-Julian Jakobitsch Stefan Haan Moritz Hiebler |
| author_sort | Stefan Rass |
| collection | DOAJ |
| description | We survey a collection of proofs towards equality, inequality, or independence of the relation of P to NP. Since the problem has attracted much attention from experts, amateurs, and in-betweens, this work is intended as a pointer into directions to enable a “self-assessment” of ideas laid out by people interested in the problem. To this end, we identify the most popular approaches to proving equality, inequality, or independence. Since the latter category appears to be without any attempts to follow the necessary proof strategies, we devote a Section to an intuitive outline of how independence proofs would work. In the other cases of proving equality or inequality, known barriers like (affine) relativization, algebrization, and others are to be avoided. The most important and powerful technique available in this regard is a formalization of arguments in automated proof assistants. This allows an objective self-check of a proof before presenting it to the scientific community. |
| first_indexed | 2024-03-08T09:43:07Z |
| format | Article |
| id | doaj.art-cd8c536b4a964b30b69f7ec3a60a50c3 |
| institution | Directory Open Access Journal |
| issn | 2169-3536 |
| language | English |
| last_indexed | 2024-03-08T09:43:07Z |
| publishDate | 2024-01-01 |
| publisher | IEEE |
| record_format | Article |
| series | IEEE Access |
| spelling | doaj.art-cd8c536b4a964b30b69f7ec3a60a50c32024-01-30T00:02:31ZengIEEEIEEE Access2169-35362024-01-0112135131352410.1109/ACCESS.2024.335554010403917Computer-Aided Verification of P/NP Proofs: A Survey and DiscussionStefan Rass0https://orcid.org/0000-0003-2821-2489Max-Julian Jakobitsch1Stefan Haan2Moritz Hiebler3LIT Secure and Correct Systems Laboratory, Johannes Kepler University Linz, Linz, AustriaInstitute for Artificial Intelligence and Cybersecurity, Universität Klagenfurt, Klagenfurt am Wörthersee, AustriaInstitute for Artificial Intelligence and Cybersecurity, Universität Klagenfurt, Klagenfurt am Wörthersee, AustriaInstitute for Artificial Intelligence and Cybersecurity, Universität Klagenfurt, Klagenfurt am Wörthersee, AustriaWe survey a collection of proofs towards equality, inequality, or independence of the relation of P to NP. Since the problem has attracted much attention from experts, amateurs, and in-betweens, this work is intended as a pointer into directions to enable a “self-assessment” of ideas laid out by people interested in the problem. To this end, we identify the most popular approaches to proving equality, inequality, or independence. Since the latter category appears to be without any attempts to follow the necessary proof strategies, we devote a Section to an intuitive outline of how independence proofs would work. In the other cases of proving equality or inequality, known barriers like (affine) relativization, algebrization, and others are to be avoided. The most important and powerful technique available in this regard is a formalization of arguments in automated proof assistants. This allows an objective self-check of a proof before presenting it to the scientific community.https://ieeexplore.ieee.org/document/10403917/P/NP questionproofsbarriersrelativizationproof assistants |
| spellingShingle | Stefan Rass Max-Julian Jakobitsch Stefan Haan Moritz Hiebler Computer-Aided Verification of P/NP Proofs: A Survey and Discussion IEEE Access P/NP question proofs barriers relativization proof assistants |
| title | Computer-Aided Verification of P/NP Proofs: A Survey and Discussion |
| title_full | Computer-Aided Verification of P/NP Proofs: A Survey and Discussion |
| title_fullStr | Computer-Aided Verification of P/NP Proofs: A Survey and Discussion |
| title_full_unstemmed | Computer-Aided Verification of P/NP Proofs: A Survey and Discussion |
| title_short | Computer-Aided Verification of P/NP Proofs: A Survey and Discussion |
| title_sort | computer aided verification of p np proofs a survey and discussion |
| topic | P/NP question proofs barriers relativization proof assistants |
| url | https://ieeexplore.ieee.org/document/10403917/ |
| work_keys_str_mv | AT stefanrass computeraidedverificationofpnpproofsasurveyanddiscussion AT maxjulianjakobitsch computeraidedverificationofpnpproofsasurveyanddiscussion AT stefanhaan computeraidedverificationofpnpproofsasurveyanddiscussion AT moritzhiebler computeraidedverificationofpnpproofsasurveyanddiscussion |