Deciding the Vapnik-Červonenkis dimension is \(\Sigma_3^p\)-complete
From MaRDI portal
Publication:1305933
DOI10.1006/jcss.1998.1602zbMath0946.68118OpenAlexW2150460548MaRDI QIDQ1305933
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
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
