scientific article; zbMATH DE number 176749

zbMATH Open0786.68045MaRDI QIDQ4036579FDOQ4036579

Authors: Desh Ranjan, Suresh Chari, Pankaj Rohatgi 

Publication date: 18 May 1993

Title of this publication is not available (Why is that?)

Recommendations

• Improving known solutions is hard
• Improving exhaustive search implies superpolynomial lower bounds
• scientific article; zbMATH DE number 4213452
• scientific article; zbMATH DE number 5310455
• Complexity of Counting the Optimal Solutions

zbMATH Keywords

randomness\(NP\)-optimizationcounterexample computation modelprobabilistic counterexample computationsPTIME transducers

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Cited In (3)

• Improving known solutions is hard
• On the complexity of incremental computation
• Improving exhaustive search implies superpolynomial lower bounds

This page was built for publication:

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