A Trial Balloon to Ban Email?

[Joseph Ashwood]

----- Original Message ----- 
From: "Paul Walker" <paul at black-sun.demon.co.uk>
Subject:  Re: A Trial Balloon to Ban Email?


> > I submit that if Joe Lunchbox is not spamming, he is unlikely to
> > need to change his habits regarding having his machine available
>
> Mostly unrelated to this, but something's just occurred to me. Probably
I'm
> being really stupid, but ... for the receiving MTA to know that the
problem
> has been processed properly, it would have to know the answer. How does it
> know what the answer should be?

That one's easy. Use a problem that is not in P but is in NP. To make it
clearer to most people, use a problem that can be verified cheaply, but that
can't be solved cheaply. Since it's only everyone's computer Minesweeper is
an example of such a problem. Once a solution has been found it is easy
enough to verify that it is correct (all bombs marked, all non-bomb places
revealed), but it can be prohibitively expensive to compute a large grid.
Other common examples include jigsaw puzzles, digits of pi, etc. More
functional puzzles for this purpose are NP-complete problems; e.g. traveling
salesman, Hamiltonian cycle, SAT, etc. Right now another couple of good
examples would be discrete logarithm, and integer factoring. In all these
cases verifying the solution is cheap (generally travelling the path in the
NP-complete problems, or computing the values in the DL and IF). Verifying
that the puzzle is valid is only slightly more difficult, but retaining an
active list of problems would solve the issue (but open up the possibility
of DOS attacks). Basically it's a fairly easily solved problem.
                        Joe