Natural proof
id:
natural-proof-312-10305989
title:
Natural proof
text:
In computational complexity theory, a natural proof is a certain kind of proof establishing that one complexity class differs from another one. While these proofs are in some sense "natural", it can be shown that no such proof can possibly be used to solve the P vs. NP problem.
brand slug:
wiki
category slug:
encyclopedia
description:
Provides lower bounds on the circuit complexity of boolean functions
original url:
https://en.wikipedia.org/wiki/Natural_proof
date created:
date modified:
2023-05-04T18:39:57Z
main entity:
{"identifier":"Q6980761","url":"https://www.wikidata.org/entity/Q6980761"}
image:
fields total:
13
integrity:
14