A note on the descriptive complexity of maximization problems

DOI10.1016/0020-0190(93)90151-XMaRDI QIDQ685495zbMATH OpenOpenAlexFDO

Authors Pilu Crescenzi, Riccardo Silvestri

Publication date 13 January 1994

Published in Information Processing Letters (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/0020-0190(93)90151-x

zbMATH Keywords

optimization problemsdescriptive complexity

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Combinatorics in computer science (68R05) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Recommendations

• Comparative versus quantitative truthlikeness definitions: Reply to Thomas Mormann
• scientific article; zbMATH DE number 1322635
• Probabilistic properties of approximation problems
• A general set theoretic approximation framework
• REASONING WITH FUZZY QUANTIFIED STATEMENTS: PART II
• On optimal approximations of arbitrary relations by partial orders
• Property-driven rough sets approximations of relations
• Approximations of arbitrary relations by partial orders
• scientific article; zbMATH DE number 4047069
• Local and Global Approximations for Incomplete Data

Cites work

• scientific article; zbMATH DE number 3474957 (Why is no real title available?)
• scientific article; zbMATH DE number 1256636 (Why is no real title available?)
• A note on the approximation of the MAX CLIQUE problem
• Approximation algorithms for combinatorial problems
• Logical definability of NP optimization problems
• Optimization, approximation, and complexity classes

Cited in

(4)

• Quantifiers and approximation
• On the Hardness of Approximating Some Optimization Problems That Are Supposedly Easier Than MAX CLIQUE
• scientific article; zbMATH DE number 4024790 (Why is no real title available?)
• AVERAGE MEASURE, DESCRIPTIVE COMPLEXITY AND APPROXIMATION OF MAXIMIZATION PROBLEMS

This page was built for publication: A note on the descriptive complexity of maximization problems

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