Check nearby libraries
Buy this book
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.
Check nearby libraries
Buy this book
Showing 2 featured editions. View all 2 editions?
Edition | Availability |
---|---|
1 |
aaaa
Libraries near you:
WorldCat
|
2 |
zzzz
Libraries near you:
WorldCat
|
Book Details
Edition 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.
The Physical Object
ID Numbers
Community Reviews (0)
Feedback?January 24, 2010 | Edited by WorkBot | add more information to works |
December 11, 2009 | Created by WorkBot | add works page |