Disclaimer: Dieser Thread wurde aus dem alten Forum importiert. Daher werden eventuell nicht alle Formatierungen richtig angezeigt. Der ursprüngliche Thread beginnt im zweiten Post dieses Threads.
Qustion regarding 10.2
We should prove, that “the problem of transforming a given formula into disjunctive normal form is NP complete”. I’m not sure what that means, since that statement is not referring to a set.
There are several things to note here.
One of the central tenants of modern mathematics is that everything is a set. A number is a set, a relation is a set, a function is a set…
So the more important question is in what sense does „the problem of transforming…“ refer to a set? Here it depends on what kind of set you expect in the context of a decision problem being NP-complete. I’m assuming you expect a problem like this to ultimately be a question of the form „is a given object x in a certain set S“? This is only marginally helpful when we deal with NP-completeness.
One of the ways people tend to think about NP-hard problems is as problems „where a solution can be verified in polynomial time, but not (necessarily) be found in polynomial time“ - one interpretation I tend to rather like, because it’s intuitive. But of course, under this interpretation a „solution“ to a „is a given object x in a certain set S“-question is simply „yes“ or „no“, in which case finding and verifying a solution are the same thing.
So here’s how I think you should think about NP problems:
The set S we want to think about is a set of pairs of inputs and valid solutions. To find a solution means: given an input I, find a value A such that the pair (I,A) is in S. To verify a solution means: given a pair (I,A), check that (I,A) is in S.
For the SAT problem, that means the inputs are formulae, the solutions are valid assignments for the formulae and S is the set of pairs (I,A) such that I is a formula and A is a valid assignment for I. Then finding an assignment for a given formula is difficult (=not polynomial), but verifying that a given assignment actually satisfies a given formula is easy (=polynomial).
For the problem in the exercise, the inputs are formulae, the solutions are equivalent formulae in DNF, and correspondingly S is the set of all pairs of formulae (I,A) such that I and A are equivalent and A is in DNF.
Hope that helps 
Another way you can think about the problem in terms of a set is to consider the set of all disjunctive normal form formulas that are equivalent to your given formula. Call this set A. Your decision problem is then the problem of deciding whether some formula beta is a member of A. You have to show that that problem is NP-complete.
Edit: This post is not quite correct. See a corrected version plus explanations here: https://fsi.cs.fau.de/forum/post/159123.