Improving known solutions is hard

DOI10.1007/BF01200119zbMath0779.68036MaRDI QIDQ687508

Suresh Chari, Desh Ranjan, Pankaj Rohatgi

Publication date: 18 October 1993

Published in: Computational Complexity (Search for Journal in Brave)

zbMATH Keywords

NP-optimization problemsmaximum cliqueLEXMAXSAT

Mathematics Subject Classification ID

Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Related Items (1)

Competing provers yield improved Karp-Lipton collapse results

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Some consequences of non-uniform conditions on uniform classes
• NP is as easy as detecting unique solutions
• The complexity of optimization problems
• Toward a unified approach for the classification of NP-complete optimization problems
• Probabilistic complexity classes and lowness
• On the complexity of unique solutions
• Relative to a Random OracleA, ${\bf P}^A \ne {\bf NP}^A \ne \text{co-}{\bf NP}^A $ with Probability 1

This page was built for publication: Improving known solutions is hard