[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
Re: Blowout
- From: Kohsuke KAWAGUCHI <k-kawa@bigfoot.com>
- To: ht@cogsci.ed.ac.uk (Henry S. Thompson), xml-dev@lists.xml.org
- 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@bigfoot.com
- References:
- Re: Blowout
- From: ht@cogsci.ed.ac.uk (Henry S. Thompson)