The NP Search Problems of Frege and Extended Frege Proofs
- Submitting institution
-
Swansea University / Prifysgol Abertawe
- Unit of assessment
- 11 - Computer Science and Informatics
- Output identifier
- 32250
- Type
- D - Journal article
- DOI
-
10.1145/3060145
- Title of journal
- ACM Transactions on Computational Logic
- Article number
- -
- First page
- 1
- Volume
- 18
- Issue
- 2
- ISSN
- 1529-3785
- Open access status
- Compliant
- Month of publication
- June
- Year of publication
- 2017
- URL
-
http://dx.doi.org/10.1145/3060145
- Supplementary information
-
-
- Request cross-referral to
- -
- Output has been delayed by COVID-19
- No
- COVID-19 affected output statement
- -
- Forensic science
- No
- Criminology
- No
- Interdisciplinary
- No
- Number of additional authors
-
-
- Research group(s)
-
-
- Citation count
- 1
- Proposed double-weighted
- No
- Reserve for an output with double weighting
- No
- Additional information
- The relationship of complexity classes like P and NP can be studied via logical approaches like length of proofs in propositional logic. A crucial step is to identify NP search problem classes that relate to logical provability. The paper invents new classes of NP search problems based on finding errors in (exponentially) large wrong propositional proofs. These are complete for logical systems of PSPACE and EXPTIME reasoning. Results immediately picked up by key researchers in area, e.g.: Goldberg and Papadimitriou, Journal of Computer and System Sciences 94, 167-192, 2018.
- Author contribution statement
- -
- Non-English
- No
- English abstract
- -