Advice classes of parametrized tractability (Q676315): Difference between revisions

Many natural computational problems have input consisting of two or more parts, one of which may be considered a parameter. For example, there are many problems for which the input consists of a graph and a positive integer. A number of results are presented concerning parametrized problems that can be solved (uniformly with respect to the parameter) in complexity classes below P, given a single word of advice for each parameter value. Different ways in which the word of advice can be employed are considered, and it is shown that the class FPT of tractable parameterized problems (the parametrized analog of P) has interesting and natural internal structure.