Connections between automatizability and learnability.
Published: 2005
Language: eng
Number of pages: 81
Description: Given a set of values of instances from a concept class, we say that we PAC-learn the concept class if we can find a function that, with high probability, evaluates random instances from that concept class with small error. We describe algorithms for the PAC-learnability of decision trees, DNF formulas and small degree polynomials. We show a connection between automatizability and PAC-learnability of DPLL versus decision trees, resolution versus DNF formulas, and polynomial calculus versus small degree polynomials.Proof systems are a method of proving unsatisfiability of CNF formulas, based on the syntactic form of the CNF, rather than the semantic one. Automatizability of a proof system implies an algorithm that finds a proof in that proof system in time polynomial in the size of the shortest proof.In the end, we give a somewhat simpler proof of [AR01] that resolution is not automatizable under complexity assumptions.
Notes: Thesis (M.Sc.)--University of Toronto, 2005.

Electronic version licensed for access by U. of T. users.

Source: Masters Abstracts International, Volume: 44-01, page: 0394.

MICR copy on microfiche.