page 2  (16 pages) 1 3

Question 1 Is there subexponential deterministic simulation of nondeterministic computation? More explicitly, is there some constant ffi < 1 such that NTIME(f(n)) ae DTIME(2O(f(n)ffi))?

Certain NP problems require only a limited amount of nondeterminism, in the sense that their (natural) NP witness is at most polylogarithmic in the input length. For such problems, improvements over exhaustive search are sometimes dramatic. Examples of problems that require limited nondeterminism can be constructed by considering parameterized versions of NP optimization problems, in which the parameter k is restricted to be small (typically constant, or O(log n)). In the examples below, k is a positive integer input parameter.

Path
Instance: A graph G of order n.
Question: Does G contain a simple path of length at least k.

Vertex Cover
Instance: A graph G of order n.
Question: Does G contain a set of vertices of cardinality at most k that is incident with every edge of G.

Clique
Instance: A graph G of order n.
Question: Does G contain a complete subgraph of order at least k.

Monotone Circuit Satisfiability
Instance: A monotone circuit C on n Boolean inputs.
Question: Does C accept an input vector of Hamming weight at most k.

Tournament Dominating Set
Instance: A digraph G = (V; E) of order n, in which for any two vertices u; v 2 V , either (u; v) 2 E or (v; u) 2 E.
Question: Find a set D ae V of minimum cardinality such that for each vertex v 2 V , there is an edge (u; v) 2 E for some vertex u 2 D.

VC Dimension
Instance: A set U of cardinality n and a family F of n subsets of U .
Question: Find a set S ae U of maximum cardinality that is shattered by F . Set S is shattered by F if for every subset T ae F there is a set A 2 F such that ATS = T .

We remark that in the last two problems above, there is no explicit parameter k involved. However, a parameter of k ' log n is implicit, since the cardinality of the optimal solution is at most log n + 1.