MNP: A class of NP optimization problems

DOI10.1007/bfb0030877zbMath1527.68077MaRDI QIDQ6085753

Qi Cheng, Unnamed Author

Publication date: 12 December 2023

Published in: Lecture Notes in Computer Science (Search for Journal in Brave)

Mathematics Subject Classification ID

Abstract computational complexity for mathematical programming problems (90C60) Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Approximation algorithms (68W25) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Cites Work

• Optimization, approximation, and complexity classes
• Reducibility among Combinatorial Problems
• Approximating maximum independent sets by excluding subgraphs
• Efficient probabilistically checkable proofs and applications to approximations
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: MNP: A class of NP optimization problems