On the complexity of test case generation for NP-hard problems

DOI10.1016/0020-0190(90)90082-9zbMath0704.68058OpenAlexW2062919621MaRDI QIDQ917311

Laura A. Sanchis

Publication date: 1990

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

Full work available at URL: https://doi.org/10.1016/0020-0190(90)90082-9

zbMATH Keywords

computational complexityNP-completenessapproximation algorithmstest case generation

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25)

Related Items

Generating hard and diverse test sets for NP-hard graph problems, The maximum clique problem

Cites Work

• Unnamed Item
• The complexity of facets (and some facets of complexity)
• An introduction to the analysis of approximation algorithms
• Optimization problems and the polynomial hierarchy
• On sparse sets in NP-P
• On the Efficient Generation of Language Instances
• Sparse Sets in : Relativizations
• The Boolean Hierarchy I: Structural Properties
• The Boolean Hierarchy II: Applications
• On Reducibility to Complex or Sparse Sets