[XML-DEV Mailing List Archive Home] [By Thread] [By Date] [Recent Entries] [Reply To This Message]

RE: ID/IDREF makes XML generation NP-hard

• To: "'ht@c...'" <ht@c...>, xml-dev@l...
• Subject: RE: ID/IDREF makes XML generation NP-hard
• From: "Bullard, Claude L (Len)" <clbullar@i...>
• Date: Fri, 28 Mar 2003 16:41:17 -0600

That's neat, Henry, and I don't mean to be mean-spirited, 
but is this a "so, but so what?" kind of thing to know? 

len

-----Original Message-----
From: ht@c... [mailto:ht@c...]

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.

• Follow-Ups:
  • Re: ID/IDREF makes XML generation NP-hard
    • From: ht@c... (Henry S. Thompson)

• Prev by Date: ID/IDREF makes XML generation NP-hard
• Next by Date: Re: ID/IDREF makes XML generation NP-hard
• Previous by thread: ID/IDREF makes XML generation NP-hard
• Next by thread: Re: ID/IDREF makes XML generation NP-hard
• Index(es):
  • Date
  • Thread