From: israel@math.ubc.ca (Robert Israel) Subject: Re: Is this problem NP complete/hard? Date: 16 Mar 2001 23:20:00 GMT Newsgroups: sci.math Summary: NP-completeness of SAT and related problems In article <98u0og$mku$1@panix3.panix.com>, kj0 wrote: >I meant to write "reducing a well-formed formula to its shortest >length." >In <98u0jv$md5$1@panix3.panix.com> kj0 writes: >>Is the problem of reducing a well-formed formula (in propositional >>calculus) NP complete or NP hard? What is the technical name for this >>problem? SAT, which is NP-complete, is the question can a given boolean formula can be made to be true by assigning true or false values to the variables? A polynomial-time algorithm for your problem would allow SAT to be solved in polynomial time: you just find the shortest equivalent to the given formula, and the answer to SAT is "true" if and only if the shortest equivalent is not "false". Therefore your problem is NP-hard. However, I don't see any way to show that your problem (made into a yes/no question in any reasonable way) is in NP. Robert Israel israel@math.ubc.ca Department of Mathematics http://www.math.ubc.ca/~israel University of British Columbia Vancouver, BC, Canada V6T 1Z2 ============================================================================== From: djimenez@cs.utexas.edu (Daniel A. Jimenez) Subject: Re: Is this problem NP complete/hard? Date: 16 Mar 2001 17:39:56 -0600 Newsgroups: sci.math In article <98u730$mva$1@nntp.itservices.ubc.ca>, Robert Israel wrote: [quote of previous message deleted --djr] This problem lies in the class NP^NP, i.e., NP with an NP oracle. I think the name of the problem is "minimum equivalent formula." Somebody's borrowed my Garey & Johnson so I can't look it up, but I know it's in there in the back of the book. -- Daniel Jimenez djimenez@cs.utexas.edu "I've so much music in my head" -- Maurice Ravel, shortly before his death. " " -- John Cage