A note on the descriptive complexity of maximization problems

DOI10.1016/0020-0190(93)90151-XzbMATH Open0778.68034OpenAlexW2052673159MaRDI QIDQ685495FDOQ685495

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

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

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)

Cites Work

• Approximation algorithms for combinatorial problems
• Optimization, approximation, and complexity classes
• Title not available (Why is that?)
• Title not available (Why is that?)
• Logical definability of NP optimization problems
• A note on the approximation of the MAX CLIQUE problem

Cited In (4)

• Quantifiers and approximation
• On the Hardness of Approximating Some Optimization Problems That Are Supposedly Easier Than MAX CLIQUE
• Title not available (Why is that?)
• 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)