Member since Jul 2016
91 posts

20190111, 10:31 #1
Subject: 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.

Member since Oct 2016
803 posts

20190111, 11:21 #2
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 NPcomplete. 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 NPcompleteness. One of the ways people tend to think about NPhard 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 
This post was edited on 20190111, 11:25 by Jazzpirate.

Member since Nov 2018
26 posts

20190111, 13:39 #3
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 NPcomplete.
Edit: This post is not quite correct. See a corrected version plus explanations here: https://fsi.cs.fau.de/forum/post/159123. 
This post was edited on 20190114, 08:22 by rappatoni.

Datenschutz 
Kontakt
Powered by the Unclassified NewsBoard software, 20150713dev,
© 20032011 by Yves Goergen