On the NP-isomorphism problem with respect to random instances

DOI10.1006/JCSS.1995.1014zbMath0827.68045OpenAlexW1967070873MaRDI QIDQ1892213

Jay Belanger, Jie Wang

Publication date: 8 June 1995

Published in: Journal of Computer and System Sciences (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1006/jcss.1995.1014

zbMATH Keywords

complexity theoryNP-isomorphism problem

Mathematics Subject Classification ID

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

Related Items (8)

The complexity of generating test instances ⋮ Average-case intractability vs. worst-case intractability ⋮ No NP problems averaging over ranking of distributions are harder ⋮ Rankable distributions do not provide harder instances than uniform distributions ⋮ Reductions and convergence rates of average time ⋮ On complete one-way functions ⋮ Complete distributional problems, hard languages, and resource-bounded measure ⋮ Polynomial time samplable distributions

This page was built for publication: On the NP-isomorphism problem with respect to random instances