Not logged in. · Lost password · Register

Jonas S
Member since Jul 2016
91 posts
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.
Jazzpirate
Member since Oct 2016
803 posts
There are several things to note here.

since that statement is not referring to a set.
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 :)
This post was edited on 2019-01-11, 11:25 by Jazzpirate.
rappatoni
Member since Nov 2018
26 posts
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.
This post was edited on 2019-01-14, 08:22 by rappatoni.
Close Smaller – Larger + Reply to this post:
Verification code: VeriCode Please enter the word from the image into the text field below. (Type the letters only, lower case is okay.)
Smileys: :-) ;-) :-D :-p :blush: :cool: :rolleyes: :huh: :-/ <_< :-( :'( :#: :scared: 8-( :nuts: :-O
Special characters:
Go to forum
Datenschutz | Kontakt
Powered by the Unclassified NewsBoard software, 20150713-dev, © 2003-2011 by Yves Goergen