PCP theorem (Q1140200)
Jump to navigation
Jump to search
theorem in complexity theory that every problem in NP has probabilistically checkable proofs
| Language | Label | Description | Also known as |
|---|---|---|---|
| English | PCP theorem |
theorem in complexity theory that every problem in NP has probabilistically checkable proofs |
Statements
![{\displaystyle NP=PCP[O(\log n),O(1)]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/e1039a409ef1fd5343eed86eb8f2043ec15b7758)
Identifiers
Sitelinks
Wikipedia(7 entries)
- dewiki PCP-Theorem
- enwiki PCP theorem
- frwiki Théorème PCP
- hewiki משפט PCP
- ptwiki Teorema PCP
- ruwiki Теорема PCP
- ukwiki PCP-теорема