ML Anthology

On the Complexity of Learning Strings and Sequences

Tao Jiang, Ming Li
COLT 1991 pp. 367-371
doi:10.1016/0304-3975(93)90167-R /colt/1991/jiang1991colt-complexity/

Abstract

It is shown that strings (sequences) cannot be learned by strings (sequences) in Valiant's distribution- free-(pac-) learning model, assuming RP ≠ NP.

COLT Semantic Scholar

Cite

Text

Jiang and Li. "On the Complexity of Learning Strings and Sequences." Annual Conference on Computational Learning Theory, 1991. doi:10.1016/0304-3975(93)90167-R

Markdown

[Jiang and Li. "On the Complexity of Learning Strings and Sequences." Annual Conference on Computational Learning Theory, 1991.](https://mlanthology.org/colt/1991/jiang1991colt-complexity/) doi:10.1016/0304-3975(93)90167-R

BibTeX

@inproceedings{jiang1991colt-complexity,
  title     = {{On the Complexity of Learning Strings and Sequences}},
  author    = {Jiang, Tao and Li, Ming},
  booktitle = {Annual Conference on Computational Learning Theory},
  year      = {1991},
  pages     = {367-371},
  doi       = {10.1016/0304-3975(93)90167-R},
  url       = {https://mlanthology.org/colt/1991/jiang1991colt-complexity/}
}