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

Re: Blowout

• From: Kohsuke KAWAGUCHI <k-kawa@b...>
• To: ht@c... (Henry S. Thompson), xml-dev@l...
• Date: Fri, 02 Mar 2001 16:35:57 -0800

3SAT is not a good problem to use here.

problem of validation can be formalized as 

input: an instance and a grammar
output: "yes" if the grammar can generate the instance
        "no" otherwise


In case of 3SAT, you are trying to find the instance that can be
generated from the grammar. In case of validation, you are given that
instance. This is a big difference.


To prove NP-completeness of the validation algorithm, we need a kind of
Yes/No problem, which can then be proven to be polynomial reducible to
the validation problem.


regards,
----------------------
K.Kawaguchi
E-Mail: k-kawa@b...

• References:
  • Re: Blowout
    • From: ht@c... (Henry S. Thompson)

• Prev by Date: RE: is that a fork in the road?
• Next by Date: Re: What is the advantage of RELAX in comparison to Schemas?
• Previous by thread: Re: Blowout
• Next by thread: Re: Blowout
• Index(es):
  • Date
  • Thread