The complexity of generating test instances

DOI10.1007/BFB0023474MaRDI QIDQ5048939zbMATH OpenFDO

Authors Christoph Karg, Rainer Schuler, Johannes Köbler

Publication date 9 November 2022

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

Full work available at URL https://doi.org/10.1007/BFB0023474

Mathematics Subject Classification ID

Searching and sorting (68P10) Analysis of algorithms and problem complexity (68Q25) Randomized algorithms (68W20)

Recommendations

• scientific article; zbMATH DE number 1332677
• scientific article; zbMATH DE number 956856
• scientific article; zbMATH DE number 1313596
• Uniform generation of NP-witnesses using an NP-oracle
• On the complexity of test case generation for NP-hard problems

Cites work

• Arthur-Merlin games: A randomized proof system, and a hierarchy of complexity classes
• Average Case Complete Problems
• Average case completeness
• Computational complexity of real functions
• Does co-NP have short interactive proofs ?
• Graph isomorphism is in the low hierarchy
• scientific article; zbMATH DE number 6084400 (Why is no real title available?)
• scientific article; zbMATH DE number 46423 (Why is no real title available?)
• scientific article; zbMATH DE number 4126690 (Why is no real title available?)
• scientific article; zbMATH DE number 512806 (Why is no real title available?)
• scientific article; zbMATH DE number 610968 (Why is no real title available?)
• scientific article; zbMATH DE number 719756 (Why is no real title available?)
• scientific article; zbMATH DE number 1072538 (Why is no real title available?)
• NP is as easy as detecting unique solutions
• On hiding information from an oracle
• On the NP-isomorphism problem with respect to random instances
• On the theory of average case complexity
• Randomizing Reductions of Search Problems
• Tally languages and complexity classes
• Universal classes of hash functions

Cited in

(4)

• The test suite generation problem: optimal instances and their implications
• scientific article; zbMATH DE number 1313596 (Why is no real title available?)
• scientific article; zbMATH DE number 1332677 (Why is no real title available?)
• scientific article; zbMATH DE number 956856 (Why is no real title available?)

This page was built for publication: The complexity of generating test instances

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