Deciding the Vapnik-Červonenkis dimension is _3p-complete

DOI10.1006/JCSS.1998.1602MaRDI QIDQ1305933zbMATH OpenOpenAlexFDO

Authors 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)

Recommendations

• Complexity of computing Vapnik-Chervonenkis dimension and some generalized dimensions
• On limited nondeterminism and the complexity of the V-C dimension
• Results on learnability and the Vapnik-Chervonenkis dimension
• On the complexity of approximating the VC dimension.

Cites work

• `` Strong NP-Completeness Results
• Approximable sets
• Density and dimension
• scientific article; zbMATH DE number 3883309 (Why is no real title available?)
• scientific article; zbMATH DE number 3888913 (Why is no real title available?)
• scientific article; zbMATH DE number 53984 (Why is no real title available?)
• scientific article; zbMATH DE number 194103 (Why is no real title available?)
• scientific article; zbMATH DE number 1351099 (Why is no real title available?)
• Learnability and the Vapnik-Chervonenkis dimension
• On a quantitative notion of uniformity
• On limited nondeterminism and the complexity of the V-C dimension
• On the Uniform Convergence of Relative Frequencies of Events to Their Probabilities
• Quantifying the amount of verboseness

Cited in

(18)

• On limited nondeterminism and the complexity of the V-C dimension
• Exact VC-dimension of Boolean monomials
• On the complexity of approximating the VC dimension.
• Dot products in \(\mathbb{F}_q^3\) and the Vapnik-Chervonenkis dimension
• A hierarchy of local decision
• Erdős-Hajnal conjecture for graphs with bounded VC-dimension
• Bounded fixed-parameter tractability and \(\log^{2}n\) nondeterministic bits
• VC Dimension Bounds for Analytic Algebraic Computations
• Beyond NP: quantifying over answer sets
• From undecidability of non-triviality and finiteness to undecidability of learnability
• A note on hardness of computing recursive teaching dimension
• The cycle discrepancy of three-regular graphs
• Computable PAC learning of continuous features
• Three \(\sum^ P_ 2\)-complete problems in computational learning theory
• Private PAC learning may be harder than online learning
• Results on learnability and the Vapnik-Chervonenkis dimension
• On product covering in 3-tier supply chain models: natural complete problems for W[3] and W[4]
• PAC learning, VC dimension, and the arithmetic hierarchy

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1305933)