From: Paul Kyzivat <[EMAIL PROTECTED]>
Can you explain more about how you reached this conclusion?
It started when I was thinking that what this draft needs (IMHO) is to
have a statement of "what the rules are", that is, the rules for
interpreting or deciding whether to accept a body, with all the rules
written in one place, so we can stare at them and see if anything is
missing. (So far, we've been writing text to explain ambiguous points
in the previous texts, but a textual structure like that makes it hard
to see if you've really covered all the cases.)
I then started to outline in my head how I would organize such a
statement:
defaulting rules for Content-Disposition
scoping and validity of 'cid'
assumptions about accepting and processing non-multipart types
accepting and processing rules for each multipart type
At that point, I noticed that there could be interdependencies between
accepting one part and accepting another part. That is usually the
signal that the problem in question is NP-complete. (In practice,
meaning that deciding what to do could take an amount of time which is
the exponential of the number of body parts to be considered, and that
the decision algorithm requires backtracking.)
So I then attempted to prove that the problem was NP-complete by the
process of reducing the problem "3-satisfiability" to the problem of
determining if a body is acceptable. And it turns out that is fairly
simple.
In order to make this construction work, I needed to assume the
following features of our body-part scheme, all of which seem to be
accepted as requirements:
If all parts of a multipart/mixed are marked handling=required,
then the body can be processed only if all the parts can be
processed.
A multipart/alternative with 2 parts can be processed if either
part can be processed, and one part must be chosen for processing,
leaving the other part un-processed.
A part can contain 'cid' URLs, which cause the referenced parts to
be processed.
A part marked "Content-Disposition: by-reference; handling=required"
can only be processed if a previous component referencing it via a
'cid' URL is processed.
What makes this situation problematic is not that deciding whether and
how to process a complex body make take exponential time (since that
will generally happen only in pathological cases), but rather that
most straightforward algorithms for making the decision will have to
implement backtracking (which will sometimes be required even in
non-pathological cases).
(Here beginneth the technical part.)
The reduction is as follows:
http://en.wikipedia.org/wiki/NP-complete
http://en.wikipedia.org/wiki/Reduction_%28complexity%29
http://en.wikipedia.org/wiki/3-satisfiability#3-satisfiability
Choose an instance of the 3-satisfiability problem, that is: a set of
boolean variables A, B, C, etc. and a formula composed of:
a series of "clauses" joined by AND, consisting of
a series of variables and their negations joined by OR.
The problem is to determine if there is any assignment of truth values
to the variables which makes the formula true, that is, which makes
true one of the variables or negations in each of the clauses.
For example, choose 4 variables A, B, C, and D, and the formula
(A OR B OR C) AND (B OR NOT-C OR D) AND (NOT-A OR NOT-B OR NOT-D)
This can be satisfied by setting A=TRUE, B=FALSE, C=TRUE, and D=FALSE.
Construct a multipart/mixed with each component labeled
handling=required. Within that, for each variable, have a part which
is multipart/alternate with 2 parts. If processing chooses the first
part of the part corresponding to a variable, that will model the
variable being TRUE. If processing chooses the second part of the
part corresponding to a variable, that will model the variable being
FALSE.
For example, our body starts:
multipart/mixed
multipart/alternative;handling=required
first part corresponding to A (not yet specified)
second part corresponding to NOT-A
multipart/alternative;handling=required
first part corresponding to B
second part corresponding to NOT-B
multipart/alternative;handling=required
first part corresponding to C
second part corresponding to NOT-C
multipart/alternative;handling=required
first part corresponding to D
second part corresponding to NOT-D
For each clause of the formula, add an additional body part, marked
"Content-Disposition: by-reference; handling=required". Give the part
a 'cid' URL. The ability of the recipient to successfully process
this part will model making the corresponding clause TRUE.
For example, our body is now:
multipart/mixed
multipart/alternative;handling=required
first part corresponding to A (not yet specified)
second part corresponding to NOT-A
multipart/alternative;handling=required
first part corresponding to B
second part corresponding to NOT-B
multipart/alternative;handling=required
first part corresponding to C
second part corresponding to NOT-C
multipart/alternative;handling=required
first part corresponding to D
second part corresponding to NOT-D
part (not otherwise
specified);by-reference;handling=required;cid=clause1
part (not otherwise
specified);by-reference;handling=required;cid=clause2
part (not otherwise
specified);by-reference;handling=required;cid=clause3
We now want to arrange things so that one of the last 3 parts can be
successfully processed only if we choose for processing one of the
earlier parts that corresponds to a variable value that will make the
corresponding clause true. This is done by embedding forward
references in the variable-corresponding parts that refer to the
clause-corresponding parts.
For example:
multipart/mixed
multipart/alternative;handling=required
first part corresponding to A
references cid:clause1
second part corresponding to NOT-A
references cid:clause3
multipart/alternative;handling=required
first part corresponding to B
references cid:clause1
references cid:clause2
second part corresponding to NOT-B
references cid:clause3
multipart/alternative;handling=required
first part corresponding to C
references cid:clause1
second part corresponding to NOT-C
references cid:clause2
multipart/alternative;handling=required
first part corresponding to D
references cid:clause2
second part corresponding to NOT-D
references cid:clause3
part;by-reference;handling=required;cid=clause1
part;by-reference;handling=required;cid=clause2
part;by-reference;handling=required;cid=clause3
In order to process this body, the recipient must choose exactly one
of each pair of bodies in the multipart/alternative body parts. This
choice is equivalent to choosing a set of values for the variables.
The references embedded in the chosen parts refer to the body parts
that correspond to the clauses which are made true by the
corresponding variable's value. In order to successfully process the
final body parts, the recipient must have chosen a set of variable
values that makes all of the clauses true.
Dale
_______________________________________________
Sip mailing list https://www.ietf.org/mailman/listinfo/sip
This list is for NEW development of the core SIP Protocol
Use [EMAIL PROTECTED] for questions on current sip
Use [EMAIL PROTECTED] for new developments on the application of sip
