Deciding the Vapnik-Červonenkis dimension is \(\Sigma_3^p\)-complete
type: Item
instance of: scholarly article
title: Deciding the Vapnik-Červonenkis dimension is \(\Sigma_3^p\)-complete
zbMATH Open document ID: 0946.68118
author: Marcus Schaefer
published in: Journal of Computer and System Sciences
publication date: 2000-10-17T00:00:00Z
Mathematics Subject Classification ID: 68T05
zbMATH DE Number: 1343336
zbMATH Keywords: Vapnik-Červonenkis dimension
MaRDI profile type: Publication
full work available at URL: jcss.1998.1602
OpenAlex ID: W2150460548
cites work: Q4004178
cites work: Density and dimension
cites work: Approximable sets
cites work: Quantifying the amount of verboseness
cites work: Learnability and the Vapnik-Chervonenkis dimension
cites work: Q3217346
cites work: `` Strong '' NP-Completeness Results
cites work: Q4267820
cites work: On a quantitative notion of uniformity
cites work: Q3221403
cites work: On limited nondeterminism and the complexity of the V-C dimension
cites work: Q4040892
cites work: On the Uniform Convergence of Relative Frequencies of Events to Their Probabilities
DOI: 10.1006/JCSS.1998.1602
description: scientific article; zbMATH DE number 1343336