[Date Prev] | [Thread Prev] | [Thread Next] | [Date Next] -- [Date Index] | [Thread Index] | [List Home]
Subject: [boblyons@unidex.com: [xml-dev] RELAX NG and datatypes make XML generation NP-hard]
----- Forwarded message from "Robert C. Lyons" <boblyons@unidex.com> ----- From: "Robert C. Lyons" <boblyons@unidex.com> To: <xml-dev@lists.xml.org> Cc: <ht@cogsci.ed.ac.uk> Date: Thu, 3 Apr 2003 08:31:21 -0500 Subject: [xml-dev] RELAX NG and datatypes make XML generation NP-hard After reading Henry's posting below, I realized that the following problem is also NP-hard: Given an arbitrary RELAX NG schema, which is allowed to contain XML Schema Datatypes, is there an XML document that conforms to the schema? Here's the proof: The 3SAT problem is NP-complete. Any 3SAT problem can be encoded into a RELAX NG schema, such that an XML document contains a solution to the 3SAT problem if and only if the document conforms to the RELAX NG schema. Thus, solving the XML generation problem (for RELAX NG with XML Schema Datatypes) is at least as hard as solving 3SAT. For example, consider the following 3SAT problem: ( x1 OR x2 OR x3 ) AND ( x2 OR NOT(x3) OR NOT(x4) ) AND ( x3 OR x4 OR NOT(x1) ) This 3SAT problem can be encoded as the following RELAX NG schema: <?xml version="1.0" encoding="UTF-8"?> <element name="three_sat_solution" xmlns="http://relaxng.org/ns/structure/1.0" datatypeLibrary= "http://www.w3.org/2001/XMLSchema-datatypes"> <data type="string"> <param name="pattern">x1=[01],x2=[01],x3=[01],x4=[01]</param> <param name="pattern">(.*x1=1.*)|(.*x2=1.*)|(.*x3=1.*)</param> <param name="pattern">(.*x2=1.*)|(.*x3=0.*)|(.*x4=0.*)</param> <param name="pattern">(.*x3=1.*)|(.*x4=1.*)|(.*x1=0.*)</param> </data> </element> The following XML document conforms to this RELAX NG schema and solves the 3SAT problem: <?xml version="1.0" encoding="UTF-8"?> <three_sat_solution>x1=1,x2=0,x3=0,x4=1</three_sat_solution> The following XML document does not conform to the RELAX NG schema and does not solve the 3SAT problem: <?xml version="1.0" encoding="UTF-8"?> <three_sat_solution>x1=1,x2=1,x3=0,x4=0</three_sat_solution> For more information on 3SAT (a.k.a., 3-CNF), see http://www.wikipedia.org/wiki/Boolean_satisfiability_problem. Since RELAX NG has a solid mathematical foundation, I suspect that the XML generation problem can be solved in linear time when the problem is restricted to RELAX NG schemas that do not use W3C XML Schema Datatypes. Best regards, Bob <sig name = 'Bob Lyons' title = 'XML and Java Consultant' company = 'Unidex, Inc.' phone = '+1-732-975-9877' email = 'boblyons@unidex.com' url = 'http://www.unidex.com/' product = 'XML Convert: transforms flat files to XML and vice versa' /> -----Original Message----- From: Henry S. Thompson [mailto:ht@cogsci.ed.ac.uk] Sent: Friday, March 28, 2003 4:59 PM To: xml-dev@lists.xml.org Subject: ID/IDREF makes XML generation NP-hard Somewhat surprisingly, it turns out that answering the question, for an arbitrary XML DTD, "Are there any valid instances of the document type defined by this DTD?", is an NP-hard problem. This is true, because it is possible to encode a 3SAT problem [1] in a DTD, so that there is an instance of the DTD's document type iff the problem can be satisfied. So finding a valid instance is as hard a problem as solving the 3SAT problem, and 3SAT is known to be NP-hard. [snip] ----------------------------------------------------------------- The xml-dev list is sponsored by XML.org <http://www.xml.org>, an initiative of OASIS <http://www.oasis-open.org> The list archives are at http://lists.xml.org/archives/xml-dev/ To subscribe or unsubscribe from this list use the subscription manager: <http://lists.xml.org/ob/adm.pl> ----- End forwarded message ----- -- John Cowan http://www.ccil.org/~cowan cowan@ccil.org To say that Bilbo's breath was taken away is no description at all. There are no words left to express his staggerment, since Men changed the language that they learned of elves in the days when all the world was wonderful. --_The Hobbit_
[Date Prev] | [Thread Prev] | [Thread Next] | [Date Next] -- [Date Index] | [Thread Index] | [List Home]