Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > KEYWORD > P-ISOMORPHISM CONJECTURE:
Reports tagged with p-isomorphism conjecture:
TR09-019 | 10th March 2009
Agrawal Manindra, Osamu Watanabe

One-Way Functions and the Isomorphism Conjecture

We study the Isomorphism Conjecture proposed by Berman and Hartmanis.
It states that all sets complete for NP under polynomial-time many-one
reductions are P-isomorphic to each other. From previous research
it has been widely believed that all NP-complete sets are reducible
each other by one-to-one and length-increasing polynomial-time
reductions, but ... more >>>




ISSN 1433-8092 | Imprint