✦ LIBER ✦

On Limited Nondeterminism and the Complexity of the V-C Dimension

✍ Scribed by Christos H. Papadimitriou; Mihalis Yannakakis

Publisher: Elsevier Science
Year: 1996
Tongue: English
Weight: 439 KB
Volume: 53
Category: Article
ISSN: 0022-0000
DOI: 10.1006/jcss.1996.0058

No coin nor oath required. For personal study only.

✦ Synopsis

We characterize precisely the complexity of several natural computational problems in NP, which have been proposed but not categorized satisfactorily in the literature: Computing the Vapnik Chervonenkis dimension of a 0 1 matrix; finding the minimum dominating set of a tournament; satisfying a Boolean expression by perturbing the default truth assignment; and several others. These problems can be solved in n O(log n) time, and thus, they are probably not NP-complete. We define two new complexity classes between P and NP, very much in the spirit of MAXNP and MAXSNP. We show that computing the V C dimension is complete for the more general class, while the other two problems are complete for the weaker class.

📜 SIMILAR VOLUMES

On the complexity of approximating the V

On the complexity of approximating the VC dimension

✍ Elchanan Mossel; Christopher Umans 📂 Article 📅 2002 🏛 Elsevier Science 🌐 English ⚖ 181 KB

We study the complexity of approximating the VC dimension of a collection of sets, when the sets are encoded succinctly by a small circuit. We show that this problem is: 3 -hard to approximate to within a factor 2 À e for all e > 0; \* approximable in AM to within a factor 2; and \* AM-hard to appr

On the effective dimension and dynamic c

On the effective dimension and dynamic complexity of earthquake faults

✍ Marian Anghel 📂 Article 📅 2004 🏛 Elsevier Science 🌐 English ⚖ 929 KB

We measure the effective dimensionality of a driven, dissipative fault model as its dynamics explore a wide parameter range from a crack like model to a dislocation model. The dynamics of each fault model are probed by recording (a) the first and second order moments of the stresses and slips define

On the complexity of some geometric prob

On the complexity of some geometric problems in unbounded dimension

✍ Nimrod Megiddo 📂 Article 📅 1990 🏛 Elsevier Science 🌐 English ⚖ 429 KB

This paper examines the complexity of several geometric problems due to unbounded dimension. The problems considered are: (i) minimum cover of points by unit cubes, (ii) minimum cover of points by unit ball% and (iii) minimum number of lines to hit a set of balls. Each of these problems is proven no

On hausdorff and topological dimensions

On hausdorff and topological dimensions of the kolmogorov complexity of the real line

✍ Jin-yi Cai; Juris Hartmanis 📂 Article 📅 1994 🏛 Elsevier Science 🌐 English ⚖ 767 KB

We investigate the Kolmogorov complexity of real numbers. Let K be the Kolmogorov complexity function; we determine the Hausdorff dimension and the topological dimension of the graph of K. Since these dimensions are different, the graph of the Kolmogorov complexity function of the real line forms a

On a complexity of the formula (A ⋁ B) ⇒

On a complexity of the formula (A ⋁ B) ⇒ C

✍ K.Yu. Gorbunov 📂 Article 📅 1998 🏛 Elsevier Science 🌐 English ⚖ 285 KB

By the complexity KF'(@) of the formula @: (A V B) \* C we mean the minimal length of a program which on input (0,A) outputs C and on input (I,@ outputs C. We prove that there exist words A, B, C such that IQ'(@) is close to K(Cl.4) + K( ClB). @ 1998-Elsevier Science B.V. Ail rights reserved K~JNVIY

On the complexity of digraph packings

✍ Richard C. Brewster; Romeo Rizzi 📂 Article 📅 2003 🏛 Elsevier Science 🌐 English ⚖ 99 KB

Let G be a fixed collection of digraphs. Given a digraph H , a G-packing of H is a collection of vertex disjoint subgraphs of H , each isomorphic to a member of G. For undirected graphs, Loebl and Poljak have completely characterized the complexity of deciding the existence of a perfect G-packing, i