Three \(\sum^ P_ 2\)-complete problems in computational learning theory

DOI10.1007/BF01200064zbMath0774.68046OpenAlexW1964858495MaRDI QIDQ685716

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 theorypattern languagesgraph reconstruction\(\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)

Related Items (4)

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

Cites Work

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

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