Approximation of coNP sets by NP-complete sets

DOI10.1007/bfb0030815zbMath1527.68079OpenAlexW1502833447MaRDI QIDQ6064009

Shuichi Miyazaki, Kazuo Iwama

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)

Cites Work

• Recognizing tough graphs is NP-hard
• Better approximations of non-Hamiltonian graphs
• Generating hard and diverse test sets for NP-hard graph problems
• The complexity of promise problems with applications to public-key cryptography
• Optimal Approximations and Polynomially Levelable Sets
• Complexity Measures for Public-Key Cryptosystems
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

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