news@ccncsu.ColoState.EDU (USENET News) (11/23/90)
of x variables. Let G(y) be the execution time of the best algorithm that takes two minimized boolean functions with at most y clauses and returns their intersection as a third minimized boolean function. Claim: if there are polynomial bounds on F and G, then P = NP. Basis: Inductive hypothesis: If there are polynomial bounds on F and G then there are polynomial bounds on the size of the third minimized boolean function of their intersection and the time required to generate it (the bound on F carries to the third minimized function.) SAT is the intersection of minimized boolean functions. If SAT can be solved in polynomial time, then so can all problems in NP, so that P = NP. So with these bounds the algorithm could generate the minimized boolean function for the intersection of the clauses sequentially, and satisfying assignments are straightforward to determine from the function. Hence the claim. What is known about F and G? Disclaimer: "If I'm not mistaken." ld231782@longs.LANCE.ColoState.EDU