I have solved problem 2 quickly by using a solution to problem 1. That’s what I call a reduction (and frankly, everyone who has ever posed this exercise to me…) - how is it not a reduction?
Btw, I dispute the claim that “every equivalent DNF is exponentially larger” as well 
depending on what exactly you mean by “EVERY equivalent”…
You’re claiming to solve SAT in polynomial time, how can that be true? Just to be sure what a „good“ reduction would look like: (to see if we’re on the same page)
My point is, that this is okay if steps 2&3 wouldn’t take 2^(|x|) steps and I do not see how to speed this up.
Poorly worded on my part. There are formulae, for which equivalent DNFs are exponentially larger. But either way it makes the reduction non-trivial.
Okay, I’ve had my cup of coffee now 
In which case you’re assuming that step 2 is exponential, correct? Which is of course true, but also basically what you’re supposed to show - that you can NOT produce a DNF in polynomial time.
Furthermore: You’re even more right to be confused in that solving the SAT problem for a DNF would be linear in the size of the DNF, but of course not in the size of the original formula (I think that’s why you were asking about the size?). This is where it makes sense to bring up the fact that an algorithm transforming a formula to a DNF would result in an exponentially larger formula.
However (please correct me if I’m wrong), a polynomial transformation to a DNF would of course result in an at most polynomial increase in size of the formula, right?
Either way: All of these are valid concerns that make the exercise more confusing than I intended it to be, so apologies for my poor framing. I actually didn’t intend for you to get hung up on the details of complexity analysis - I thought I subverted that by giving the hints as a guideline what I expected you to actually do, hoping that students NOT familiar with complexity analysis wouldn’t be confused. Apparently, I instead confused the students that WERE familiar with complexity
See here why the runtime is exponential Disjunctive normal form - Wikipedia.
So we should just forget about all the complexity stuff and transform arbitrary formulae to DNFs?
Yes that is true, but that is not easy (if at all possible ds.algorithms - Why is CNF used for SAT and not DNF? - Theoretical Computer Science Stack Exchange claims it isn’t).
Yes, I know it is 
Well, not really. But remember: The goal is to show that reducing formulae to DNF is NP-hard. The way to go about this is to show that if there WERE a non-NP-hard algorithm (i.e. in particular sub-exponential), then we COULD subsequently solve SAT in polynomial time (linear even, in the size of the DNF), contradiction.
I.e. to (correctly) assume that it is exponential is to already assume what you’re supposed to prove.
Does that make sense?
Oh yeah, I get it now. Thanks for your answers.
OK, great 
Either way, the problem wasn’t framed well, so if there’s any more confusion let me know - it’s quite possible I got more things wrong there 
Okay nvm still unclear: (I hope I’m not a total idiot and overlook something obvious)
You’re assuming two different things here.
The latter statement is the assumption that DNF is in P. A contradiction with this statement is easy, but doesn’t prove anything interesting.
So assuming non-NP-hardness, I don’t see how we can arrive at a contradiction, since there may well be problems which need exponential time to reduce to DNF.
Edit: Can we prove non-NP-hardness? Because if it were, we could solve SAT in polynomial time!?
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 NP-hard, which probably isn’t the ideal solution but I think it works.
but how do you do that in polynomial time?
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 NP-hard. 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 NP-hard because SAT is NP-complete.
Those two statements contradict each other.
Also:
@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 NP-complete, 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?
You are confusing two things here.
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/Polynomial-time_reduction#Many-one_reductions
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?
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.
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.
What do you mean by „inputs“?
That’s exactly the problem (see the last two post).
Rather think of it as converting the solution of the DNF-problem back to a solution for the SAT-problem.
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 (well-known) equivalent definitions of the complexity class NP. Firstly, it is the class of problems that a Non-deterministic 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 non-deterministic choices in polynomial time and then run the verifier.)
Indeed, we should have framed it differently. In fact, my post Qustion regarding 10.2 - #4 von rappatoni - Künstliche Intelligenz - FSI Informatik Forum 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 NP-hard. 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 NP-complete (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 NP-hard 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 non-deterministic one. If you are supposed to prove that some search problem is say NP-complete, any overhead that is in NP will not matter. Hence if you can prove that the decision problem is NP-hard 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 SAT-problem the difference between decision and search does not matter in terms of complexity).
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 NP-complete. In fact it is at least Co-NP hard. (I found the following proof here: cc.complexity theory - Is DNF-Equivalence Problem $\mathsf{NP\mbox{-Hard}}$? - Theoretical Computer Science Stack Exchange). 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 NP-complete, checking whether a CNF is valid is Co-NP-complete (I won’t go into the definition of Co-NP here but it is usually much „worse“ than NP (although it is not known that NP!=Co-NP). 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).
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 NP-problems can be solved in polynomial time (P=NP?). Less well known it is also not currently known whether all NP-hard problems have at least exponential runtime if P!=NP. Note that sub-exponential != polynomial (sub-exponential 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 NP-hard (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 NP-hard.