Is it possible to speed up addition of "not null"?

I have 8.3 database with non-trivial table (~ 80million rows, but the
rows are just two integers).

I need to add not null on one of the columns, but it seems to require
full table scan.

I tried with some indexes, but I can't get the time to something
reasonable, so here is my question: is there any way I could make the
"not null" constraint *fast*?

i need it to be able to run pg_reorg on this table, which requires pkey,
or unique index on not-null column.

Best regards,

depesz

--
The best thing about modern society is how easy it is to avoid contact with it.
                                                             http://depesz.com/