Three ^ P_ 2-complete problems in computational learning theory

DOI10.1007/BF01200064zbMATH Open0774.68046OpenAlexW1964858495MaRDI QIDQ685716FDOQ685716

Wen-Guey Tzeng, Ker-I Ko

Publication date: 10 October 1993

Published in: Computational Complexity (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/bf01200064

zbMATH Keywords

computational learning theorygraph reconstructionpattern languages\(\Sigma_ 2^ P\)-completeness

Mathematics Subject Classification ID

Learning and adaptive systems in artificial intelligence (68T05) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Learnability and the Vapnik-Chervonenkis dimension
• Learning regular sets from queries and counterexamples
• Finding patterns common to a set of strings
• Equivalences Among Relational Expressions with the Union and Difference Operators
• A theory of the learnable
• The polynomial-time hierarchy
• The complexity of combinatorial problems with succinct input representation
• Computational limitations on learning from examples
• Complete sets and the polynomial-time hierarchy
• Prediction-preserving reducibility
• A note on the two-variable pattern-finding problem

Cited In (4)

• Revisiting Shinohara's algorithm for computing descriptive patterns
• On learning unions of pattern languages and tree patterns in the mistake bound model.
• Graph Ramsey theory and the polynomial hierarchy
• In Memoriam: Ker-I Ko (1950–2018)

This page was built for publication: Three \(\sum^ P_ 2\)-complete problems in computational learning theory

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