Copmutationally Sound Proofs
This paper puts forward a new notion of a proof based on computational complexity and explores its implications for computation at large. Computationally sound proofs provide, in a novel and meaningful framework, answer to old and new questions in complexity theory. In particular, given a random ora...
| Main Author: | |
|---|---|
| Published: |
2023
|
| Online Access: | https://hdl.handle.net/1721.1/149277 |
| _version_ | 1826206382871805952 |
|---|---|
| author | Micali, Silvio |
| author_facet | Micali, Silvio |
| author_sort | Micali, Silvio |
| collection | MIT |
| description | This paper puts forward a new notion of a proof based on computational complexity and explores its implications for computation at large. Computationally sound proofs provide, in a novel and meaningful framework, answer to old and new questions in complexity theory. In particular, given a random oracle or a new complexity assumption, they enable us to 1. prove that verifying is easier than deciding for all theorems; 2. provides a quite effective way to prove membership in computationally hard languages (such as C-NP-complete ones); and 3. show that every computation possesses a short certificate vouching its correctness. FInally, if a special type of computationally sound proof exists, we show that Blum's notion of program checking can be meaningfully broadened so as to prove that NP-complete languages are checkable. |
| first_indexed | 2024-09-23T13:28:59Z |
| id | mit-1721.1/149277 |
| institution | Massachusetts Institute of Technology |
| last_indexed | 2024-09-23T13:28:59Z |
| publishDate | 2023 |
| record_format | dspace |
| spelling | mit-1721.1/1492772023-03-30T03:37:54Z Copmutationally Sound Proofs Micali, Silvio This paper puts forward a new notion of a proof based on computational complexity and explores its implications for computation at large. Computationally sound proofs provide, in a novel and meaningful framework, answer to old and new questions in complexity theory. In particular, given a random oracle or a new complexity assumption, they enable us to 1. prove that verifying is easier than deciding for all theorems; 2. provides a quite effective way to prove membership in computationally hard languages (such as C-NP-complete ones); and 3. show that every computation possesses a short certificate vouching its correctness. FInally, if a special type of computationally sound proof exists, we show that Blum's notion of program checking can be meaningfully broadened so as to prove that NP-complete languages are checkable. 2023-03-29T14:40:47Z 2023-03-29T14:40:47Z 2000 https://hdl.handle.net/1721.1/149277 MIT-LCS-TM-577 application/pdf |
| spellingShingle | Micali, Silvio Copmutationally Sound Proofs |
| title | Copmutationally Sound Proofs |
| title_full | Copmutationally Sound Proofs |
| title_fullStr | Copmutationally Sound Proofs |
| title_full_unstemmed | Copmutationally Sound Proofs |
| title_short | Copmutationally Sound Proofs |
| title_sort | copmutationally sound proofs |
| url | https://hdl.handle.net/1721.1/149277 |
| work_keys_str_mv | AT micalisilvio copmutationallysoundproofs |