The Complexity Landscape of Boolean Formula Isomorphism: From Graph Isomorphism to the Second Level
यह शोध पत्र कैनोनिकल फॉर्मूला आइसोमोर्फिज्म (canonical formula isomorphism) और ग्राफ आइसोमोर्फिज्म के बीच एक द्विदिश मेनी-वन तुल्यता (bidirectional many-one equivalence) स्थापित करते हुए, को-एनपी-कम्प्लीट (coNP-complete) समानता परीक्षण और अवशिष्ट ग्राफ आइसोमोर्फिज्म कोर के संयोजन के कारण सामान्य फॉर्मूला आइसोमोर्फिज्म के दूसरे स्तर () पर स्थित होने को प्रदर्शित करते हुए, पॉलीनोमियल पदानुक्रम (polynomial hierarchy) के भीतर बुलियन फॉर्मूला आइसोमोर्फिज्म की जटिलता को सटीक रूप से वर्गीकृत करता है।