Re: Last Call: SMTP Service Extension for Content Negotiation to Proposed Standard

Graham Klyne <[email protected]> Thu, 04 Jul 2002 23:17:25 +0100

Newsgroups	gmane.ietf.fax
Message-ID	<[email protected]>

I am pretty confident this is not the case with CONNEG feature 
matching.  At worst, I think it's polynomial in the size of the feature 
expression, and typically closer to linear.

The worst-case arises when expressions contain repeated conjunctions of 
disjunctions which lead to a multiplicity of conjunctions when reduced to 
the disjunctive normal form.

#g
--

At 01:41 AM 7/4/2002 -0400, John C Klensin wrote:
>   With a
>sufficiently complex (non-binary and non-orthogonal) capability
>set, I suspect the computation might even turn out to be
>NP-hard.

-------------------
Graham Klyne
<[email protected]>