# how is time complexity defined in computational learning theory

In general, when we say an algorithm $$A$$ PAC learns $$C$$ in time $$t$$, we say $$A$$ takes time $$t$$ before outputting a hypothesis $$h$$, and the hypothesis can be evaluated (on every $$x$$) in time $$t$$.

Now how is the hypothesis output? In the sense, should the learner write down the truth table/ circuit description? Is the time in describing the hypothesis included in $$t$$? Or does one only worry about how long it takes to evaluate $$h$$? If the output is a truth table, can't every hypothesis be evaluated in time $$1$$ already?

• I will let someone who is more of an expert on learning theory answer, but let me say that all of these are valid concerns and, as far as I remember, are nicely discussed in Kearns and Vazirani's Computational Learning Theory book. Usually you fix a way to represent a concept (which is almost never a truth table, but could be a circuit) so that the concept can be evaluated efficiently from the representation. Then an efficient learner is allowed to run in time polynomial in the size of the smallest representation. – Sasho Nikolov Mar 24 at 16:52
• To complement what @SashoNikolov wrote: this is Section 1.2 of the Kearns—Vazirani book, discussing the representation scheme. See Definition 2 "(The PAC model, Modified Definition)" which incorporates it. – Clement C. Mar 28 at 18:30