ML Anthology

Can Complexity Theory Benefit from Learning Theory?

Tibor Hegedüs
ECML-PKDD 1993 pp. 354-359
doi:10.1007/3-540-56602-3_150 /ecmlpkdd/1993/hegedus1993ecml-complexity/

Abstract

We show that the results achieved within the framework of Computational Learning Theory are relevant enough to have non-trivial applications in other areas of Computer Science, namely in Complexity Theory. Using known results on efficient query-learnability of some Boolean concept classes, we prove several (co-NP-completeness) results on the complexity of certain decision problems concerning representability of general Boolean functions in special forms.

PDF ECML-PKDD Semantic Scholar

Cite

Text

Hegedüs. "Can Complexity Theory Benefit from Learning Theory?." European Conference on Machine Learning, 1993. doi:10.1007/3-540-56602-3_150

Markdown

[Hegedüs. "Can Complexity Theory Benefit from Learning Theory?." European Conference on Machine Learning, 1993.](https://mlanthology.org/ecmlpkdd/1993/hegedus1993ecml-complexity/) doi:10.1007/3-540-56602-3_150

BibTeX

@inproceedings{hegedus1993ecml-complexity,
  title     = {{Can Complexity Theory Benefit from Learning Theory?}},
  author    = {Hegedüs, Tibor},
  booktitle = {European Conference on Machine Learning},
  year      = {1993},
  pages     = {354-359},
  doi       = {10.1007/3-540-56602-3_150},
  url       = {https://mlanthology.org/ecmlpkdd/1993/hegedus1993ecml-complexity/}
}