Page: ‹ previous 1 2
Member since Jan 2019
6 posts

20190112, 12:02 #16
In reply to post ID 159104
Responding to one of your earlier posts. Firstly, you need a polynomial time reduction, that only means that you have to convert inputs from one problem to the other in polynomial time.
The way I went about this (which is still kinda wonky) is then make an algorithm that decides satisfiability by converting to DNFs first, then we can easily transform problems from SAT into problems for our new algorithm (in fact we can do it in O(1) since it is exactly the same inputs). Then the reduction works and we know that going through DNFs must also be NP hard (duh, since our algorithm is an instance of SAT...). Then I argued what part of the SAT through DNF algorithm made it NPhard, which probably isn't the ideal solution but I think it works. 
Member since Jul 2016
91 posts

20190112, 12:20 #17
but how do you do that in polynomial time? 
Member since Jan 2019
6 posts

20190112, 12:29 #18
The entire point of this assignment is to show that (under the assumption of P != NP) you cannot do it in polynomial time, i.e. it is at least NPhard. The standard way of showing this is through polynomial time reductions, where you reduce SAT to the given problem. If you can solve SAT using our new problem (by converting inputs in polynomial time), then it means that our problem must be at least as hard as SAT, thus our problem is at least NPhard because SAT is NPcomplete.

Member since Jul 2016
91 posts

20190112, 12:40 #19
Those two statements contradict each other. Also:

Member since Oct 2016
803 posts

20190112, 12:42 #20
In reply to post #16
@Fredy that's what I was going for, yes
@Jonas S: And you're right again, I mixed things up. Although: There can't, because SAT in NPcomplete, and we can reduce SAT to DNF in polynomial time. The reduction from SAT to DNF is merely adding the "solve SAT for the resulting DNF"step. So the exercise is basically to show that this added step is at most polynomial, so that the reduction itself is polynomial. < Maybe this argument is more helpful. Probably forget what I said about contradictions,this might be another cause for unnecessary confusion. Or am I now confused about something again? 
Member since Jan 2019
6 posts

20190112, 12:47 #21
In reply to post #19
You are confusing two things here.
1. You cannot convert formulas to DNFs in polynomial time, because as you already pointed out you have potential exponential blowup. 2. You can however write a reduction function, that converts the inputs of SAT to inputs of SAT through DNFs in polynomial time (the inputs are exactly the same). This reduction function is all that is required to run in polynomial time for the reduction to work. Note that the reduction function does NOT solve the underlying problem, but only converts inputs from one problem to the other. See here: https://en.wikipedia.org/wiki/Polynomialtime_reduction#Ma… 
Member since Oct 2016
803 posts

20190112, 12:54 #22
Correct me if I'm wrong: converts inputs from one problem to the other one AND converts a solutions for the latter to a solution for the former? 
Member since Jan 2019
6 posts

20190112, 13:00 #23
Typically we are dealing with decision problems, so the outputs are always yes/no and therefore do not have to be converted.
This focus on decision problems is exactly what makes this assignment a bit confusing, since converting formulas to DNFs is not a decision problem and I wasn't able to come up with an equivalent decision problem (for example checking whether or not a formula is DNF is clearly in P). I actually maybe came up with a suitable decision problem: You are given a formula and a formula in DNF and you have to decide if the formula's DNF is the given DNF. I don't think reducing SAT to that problem is the aim of that assignment though and I wouldn't even know how to start. 
This post was edited on 20190112, 13:10 by Fredy.

Member since Oct 2016
803 posts

20190112, 13:14 #24
OK, then we're on the same page, thank you
Yes, that's why I tried to direct the focus away from framing this as a decision problem Minor correction that makes this awkward again: DNFs are not unique. A formula can have many different equivalent DNFs, and to check whether a formula D is *a* DNF for a formula A is certainly different than finding *any* DNF for A. 
Member since Jul 2016
91 posts

20190112, 13:15 #25
In reply to post #21
What do you mean by "inputs"? 
Member since Oct 2016
803 posts

20190112, 13:17 #26
That's exactly the problem (see the last two post). Rather think of it as converting the solution of the DNFproblem back to a solution for the SATproblem. 
Member since Nov 2018
26 posts

20190114, 08:21 #27
+1 Jazzpirate
I think it may help to go to the level of definitions to clear up a few confusions in this discussion. So let me put them here first:
There are two (wellknown) equivalent definitions of the complexity class NP. Firstly, it is the class of problems that a Nondeterministic Turing machine (NDTM) can solve in Polynomial time. Secondly, it is the class of problems for which there exists a certificate of polynomial length, i.e. a string of bits of polynomial length given which a deterministic Turing machine (DTM) (called the verifiers) can solve the decision problem in polynomial time. (Aside: That the two definitions are in fact equivalent can be seen by considering that the number of decisions an NDTM has to make to solve the problem in polynomial time has to be polynomial and thus the writing down those decisions as a string of bits will yield a certificate of polynomial length that helps a DTM to do the same thing in polynomial time. Conversely, an NDTM can just find a certificate by making nondeterministic choices in polynomial time and then run the verifier.) 1. Search Problems vs Decision Problems
Indeed, we should have framed it differently. In fact, my post https://fsi.cs.fau.de/forum/post/159069 was incorrect in that regard. However, in the amended question you are only supposed to prove that the search problem of finding a DNF equivalent to a given formula \phi is NPhard. In contrast to that the decision problem would correspond to deciding whether any DNF (formula, string) \psi is in the set of DNFs that are equivalent to \phi. There is an (exponential) algorithm to convert any NDTM solving the decision problem into one for solving the search problem. It looks like this: Given \phi, a NDTM can find an assignment in polynomial time as SAT is NPcomplete (for SAT, the search problem and the decision problem are equivalent. Why? see below). We can then check nondeterministically in polynomial time whether that assignment is equivalent to \phi (as a single conjunction is a DNF). If not we proceed by finding another assignment, and check the resulting disjunction of the first and the second assignment. And so forth (potentially exponentially many times). Hence it is sufficient to prove that the decision problem is NPhard and you are done. (The reason for my mistake is that often in complexity theory the difference between search and decision problems does not matter. Often there exists a polynomial reduction of the search problem to the decision problem or at least a nondeterministic one. If you are supposed to prove that some search problem is say NPcomplete, any overhead that is in NP will not matter. Hence if you can prove that the decision problem is NPhard and there is an NDTM that calls the solver for the decision problem polynomially many times to solve the search problem, then you have proved that the search problem is in the same complexity class as the decision problem. Edit: For SAT an algorithm exists that calls the solver for the decision problem linearly many times (it is a nice exercise to figure it out). Hence for the SATproblem the difference between decision and search does not matter in terms of complexity). 2.
Given the above definitions showing that a problem is in NP is usually easy: you just need to find a suitable certificate and mostly it is obvious what that certificate should be (in SAT for example, a satisfying assignment does the trick). In this case however, it is not clear what the certificate should be. One might consider a valid reduction from \phi to \psi but we have no guarantee that this reduction is polynomial in the length of \psi. Indeed, Fredy is right that this decision problem is not NPcomplete. In fact it is at least CoNP hard. (I found the following proof here: https://cstheory.stackexchange.com/questions/19434/isdnf…). For consider the special case where \phi is a tautology. For a DNF to be a tautology it's negation must be unsatisfiable. Negating a DNF yields a CNF. As checking whether a CNF is satisfiable is NPcomplete, checking whether a CNF is valid is CoNPcomplete (I won't go into the definition of CoNP here but it is usually much "worse" than NP (although it is not known that NP!=CoNP). You can see that by considering that to find out whether a formula is valid you have to check all of its possible assignments whereas for satisfiability you only need to find one). 3. NP and exponential time
That is not the same assumption. As you can see from the above definitions, NP is not defined in terms of exponential time. As you know, it is not known whether NPproblems can be solved in polynomial time (P=NP?). Less well known it is also not currently known whether all NPhard problems have at least exponential runtime if P!=NP. Note that subexponential != polynomial (subexponential meaning "smaller than 2^(n^o(1)). That they do is called the exponential time hypothesis which most complexity theorists believe to be true (although that belief is much weaker than the belief that P!=NP). Proving that a problem is EXPtime hard is usually much harder than proving it is NPhard (you have to show that there is NO subexponential algorithm). So in general try to think in terms of NDTMs and certificates when proving that something is in NP and in terms of reductions when proving that something is NPhard. 
This post was edited on 20190114, 12:59 by rappatoni.

Page: ‹ previous 1 2
Datenschutz 
Kontakt
Powered by the Unclassified NewsBoard software, 20150713dev,
© 20032011 by Yves Goergen