Non Permutation Dependent

There are lots of PermutationDependent data formats. For example, a graph's connectivity matrix is hideously permutation dependent. Shuffle the rows and columns and suddenly detecting obvious features, like MaximumClique, becomes an NpComplete problem.

SaulAmarel showed how to take one of these NpComplete problems, the CannibalsAndMissionaries, and take the complexity out of it by decomposing it into a NonPermutationDependent representation.

Unfortunately, he was never able to do this for any other problem ...

One of the BenefitsOfXml is that, at least in principle, it makes hierarchical data representations NonPermutationDependent. And in practice that's a lot better than just making them into plain text.

Wha'? I don't understand. Please explain more clearly.

In the case of a graph, GraphTheory doesn't care about node labelling; so lots of permutations of a connectivity matrix are equivalent to the same graph. The connectivity matrix is PermutationDependent.

The problem of finding a MaximumClique, then, appears to be an artifact of the representation used. No one has been able to come up with a NonPermutationDependent representation of a graph, so we're stuck with the silly fact that MaximumClique (and all its equivalent problems) is NpComplete.

And that's why the trains don't run on time.

Shucks, we know that's why timetables cause infernal complexities. Are you try'na say that an XML file contains identical labels, so the order from top to bottom of them labels don't matter? But you can say that about a flat tab-separated text file.

No, silly, I'm trying to provoke someone into correcting me so I can go back into wale-on-XML mode. I woke up this morning and wanted to give XML a good old poke. Then regrettably figured out some real BenefitsOfXml ... though in this particular respect XML ain't exactly what you'd call consistent ... <li><li><li> ...

Sorry, but you're confusin' me. You seem to be sayin' "XML is good because it supports NonPermutationDependent hierarchical data. But so does plain-old-text, so it doesn't really matter." And exactly what does this have to do with finding the MaximumClique or solving other NpComplete problems -- if we start using XML, is it going to make the trains all run on time?

---

Maybe the creator of this page is missing something, but XML really is order dependent.

It is the most stupid data model in this regard (worse than the old IMS), because it makes the physical order of unrelated data crucially important. Try to change the order of unrelated elements for example in web.xml in a web application, and your Tomcat/Websphere/Weblogic whatever will refuse to start, even if it has all the needed and correct information in there. It's just not in the physical order it expects. It really sucks.

Thank you! But isn't this really a problem with Tomcat/Websphere/Weblogic rather than a problem with XML?

No, it is a problem with XML defined semantics. That by default physical data ordering is important.:

   <person>
    <first_name>F</firstname>
    <last_name>L</lastname>
   </person>

is semantically different than

   <person>
    <last_name>L</lastname>
    <first_name>F</firstname>
   </person>

to make matters only worse, it is still different than

   <person first_name="F" last_name="L" />

Data integration solutions, you think ? Be ready to write lots and lots of XSL. Be ready to buy the latest and greatest hardware to swallow all that unnecessary extra tag garbage.

What? Well then XmlPermutationDependenceSucks!!!

No it does not. Sometimes the order is relevant and XML allows you to evaluate the order of the tags. (It no not does. Evaluate order the tags of the the relevant XML you sometimes is allows order.)