[XML-DEV Mailing List Archive Home] [By Thread] [By Date] [Recent Entries] [Reply To This Message] 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. regards, ---------------------- K.Kawaguchi E-Mail: k-kawa@b...
|
PURCHASE STYLUS STUDIO ONLINE TODAY!Purchasing Stylus Studio from our online shop is Easy, Secure and Value Priced! Download The World's Best XML IDE!Accelerate XML development with our award-winning XML IDE - Download a free trial today! Subscribe in XML format
|