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.
10.2 NP-Complete?
I don’t think the information given in the hint of Problem 10.2 is correct. If my understanding of complexity theory is still somewhat correct (and admittedly it’s been a few years), reducing SAT to a problem in polynomial time only proves that a problem is NP hard, but NP completeness also requires the problem being a member of NP. For example, the satisfiability problem of the modal mu calculus is EXPTIME complete, but we can clearly reduce SAT to it in polynomial time.
Additionally, I am not entirely sure we can show that converting formulas to CNFs (or whatever the equivalent decision problem is?), is a member of NP. After all, the input formula has polynomial size while the output formula has exponential size. A ton of googling has also not revealed a single proof showing membership of NP (only NP hardness).
Perfectly correct.
You might be right there as well. Honestly, the point of the exercise was just to show NP hard (see the hints- that’s basically all you are supposed to do, and Hint 2 implies NP-hardness). I naively assumed that NP completeness would follow trivially, but thinking about it I realize it absolutely doesn’t. Sorry about that.
So ignore that part about NP completeness 
1 „Gefällt mir“
Follow up question: how can we reduce SAT to the DNF-language if every equivalent DNF is exponentially larger?
I don’t understand…? You can reduce a problem to another problem by showing that a solution to the latter yields a solution to the former. This has nothing to do with the sizes of formulae.
But to show NP-hardness this reduction has to be in polynomial time, and then size matters.
No, it doesn’t 
Given a formula in DNF, I can solve its SAT problem in polynomial time. The size of the formula doesn’t come into play whatsoever.
I get that, but that’s not a reduction?
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)
- We get an instance x of SAT
- We reduce it to a DNF
- We solve the DNF
- We now have a solution x
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.
- [quote]
if there WERE a non-NP-hard algorithm
[/quote]
Assuming non-NP-hardness means, that there exist problems in NP which cannot be reduced to DNF in polynomial time. Which is not the same as
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: