Approximation of coNP sets by NP-complete sets

DOI10.1007/BFB0030815MaRDI QIDQ6064009zbMATH OpenOpenAlexFDO

Authors Kazuo Iwama, Shuichi Miyazaki

Publication date 12 December 2023

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

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

Mathematics Subject Classification ID

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

Recommendations

• Completeness in approximation classes
• Optimal Approximations and Polynomially Levelable Sets
• scientific article; zbMATH DE number 847149
• scientific article; zbMATH DE number 17535
• scientific article; zbMATH DE number 515727

Cites work

• Better approximations of non-Hamiltonian graphs
• Complexity Measures for Public-Key Cryptosystems
• Generating hard and diverse test sets for NP-hard graph problems
• scientific article; zbMATH DE number 3912424 (Why is no real title available?)
• scientific article; zbMATH DE number 46423 (Why is no real title available?)
• scientific article; zbMATH DE number 1256654 (Why is no real title available?)
• scientific article; zbMATH DE number 1404230 (Why is no real title available?)
• scientific article; zbMATH DE number 956856 (Why is no real title available?)
• Optimal Approximations and Polynomially Levelable Sets
• Recognizing tough graphs is NP-hard
• The complexity of promise problems with applications to public-key cryptography

Cited in

(6)

• NP-completeness of small conflict set generation for congruence closure
• scientific article; zbMATH DE number 6474898 (Why is no real title available?)
• The Shrinking Property for NP and coNP
• NP-Creative sets: A new class of creative sets in NP
• A Theory of NP-completeness and Ill-conditioning for Approximate Real Computations
• The shrinking property for NP and coNP

This page was built for publication: Approximation of coNP sets by NP-complete sets

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