Deciding the Vapnik-Červonenkis dimension is \(\Sigma_3^p\)-complete

DOI10.1006/jcss.1998.1602zbMath0946.68118OpenAlexW2150460548MaRDI QIDQ1305933

Marcus Schaefer

Publication date: 17 October 2000

Published in: Journal of Computer and System Sciences (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1006/jcss.1998.1602

zbMATH Keywords

Vapnik-Červonenkis dimension

Mathematics Subject Classification ID

Learning and adaptive systems in artificial intelligence (68T05)

Related Items (10)

On the complexity of approximating the VC dimension. ⋮ On product covering in 3-tier supply chain models: natural complete problems for W[3 and W[4]] ⋮ Erdős-Hajnal conjecture for graphs with bounded VC-dimension ⋮ PAC learning, VC dimension, and the arithmetic hierarchy ⋮ From undecidability of non-triviality and finiteness to undecidability of learnability ⋮ A note on hardness of computing recursive teaching dimension ⋮ Beyond NP: Quantifying over Answer Sets ⋮ A hierarchy of local decision ⋮ The cycle discrepancy of three-regular graphs ⋮ Bounded fixed-parameter tractability and \(\log^{2}n\) nondeterministic bits

Cites Work

• On limited nondeterminism and the complexity of the V-C dimension
• Density and dimension
• Quantifying the amount of verboseness
• Approximable sets
• Learnability and the Vapnik-Chervonenkis dimension
• On a quantitative notion of uniformity
• `` Strong NP-Completeness Results
• On the Uniform Convergence of Relative Frequencies of Events to Their Probabilities
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: Deciding the Vapnik-Červonenkis dimension is \(\Sigma_3^p\)-complete