Computational learning theory: Difference between revisions

Revision as of 15:05, 20 January 2006

Revision as of 17:41, 21 June 2006

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 - [[Complexity classes P and NP|P]]<math>\neq</math>&ne;[[Complexity classes P and NP|NP]]

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