OASIS Mailing List ArchivesView the OASIS mailing list archive below
or browse/search using MarkMail.


Help: OASIS Mailing Lists Help | MarkMail Help

[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

Re: Blowout

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.

E-Mail: k-kawa@bigfoot.com