Computational learning theory: Difference between revisions

Revision as of 13:20, 27 October 2005

Revision as of 15:05, 20 January 2006

Line 6:

#Positive results --- Showing that a certain class of functions is learnable in polynomial time.

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

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

* Computational complexity - [[Complexity classes P and NP|P]]<math>\neq</math>[[Complexity classes P and NP|NP]]

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