Three ^ P_ 2-complete problems in computational learning theory

DOI10.1007/BF01200064MaRDI QIDQ685716zbMATH OpenOpenAlexFDO

Authors 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

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

Mathematics Subject Classification ID

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

Recommendations

• Finding tree patterns consistent with positive and negative examples using queries
• Computational limitations on learning from examples
• scientific article; zbMATH DE number 2077169
• scientific article; zbMATH DE number 5957227
• Deciding the Vapnik-Červonenkis dimension is \(\Sigma_3^p\)-complete

Cites work

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

Cited in

(10)

• On learning unions of pattern languages and tree patterns in the mistake bound model.
• Revisiting Shinohara's algorithm for computing descriptive patterns
• Finding a minimal 1-DNF consistent with a positive sample is LOGSNP-complete
• In Memoriam: Ker-I Ko (1950–2018)
• scientific article; zbMATH DE number 2080215 (Why is no real title available?)
• scientific article; zbMATH DE number 1786549 (Why is no real title available?)
• Graph Ramsey theory and the polynomial hierarchy
• Learning from positive and negative examples: new proof for binary alphabets
• The complexity of homomorphism reconstructibility
• The complexity of homomorphism reconstructibility

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)