ADVICE CLASSES OF PARAMETERIZED TRACTABILITY

Many natural computational problems have input consisting of two or mo re parts, one of which may be considered a parameter. For example, the re are many problems for which the input consists of a graph and a pos itive integer. A number of results are presented concerning parameteri zed problems that can be solved (uniformly with respect to the paramet er) in complexity classes below P, given a single word of advice for e ach parameter value. Different ways in which the word of advice can be employed are considered, and it is shown that the class FPT of tracta ble parameterized problems (the parameterized analog of P) has interes ting and natural internal structure.