Computational learning theory: Difference between revisions

Revision as of 19:45, 14 August 2007

Revision as of 10:16, 21 August 2007

Line 7:

#Negative results - Showing that certain classes cannot be learned in polynomial time.

Negative results are proven only by assumption. The assumptions that are common in negative results are:

* Computational complexity - [[P=NP problem|P]] ≠[[P=NP problem|NP]]

* [[cryptography|Cryptographic]] - [[One-way function]]s exist.