Member since Jan 2019
6 posts

20190111, 21:59 #1
Subject: 10.2 NPComplete?
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). 
Member since Oct 2016
803 posts

20190111, 22:25 #2
+1 Fredy
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 NPhardness). 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 
Member since Jul 2016
91 posts

20190111, 23:21 #3
Follow up question: how can we reduce SAT to the DNFlanguage if every equivalent DNF is exponentially larger?

Member since Oct 2016
803 posts

20190112, 08:48 #4
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. 
Member since Jul 2016
91 posts

20190112, 08:51 #5
But to show NPhardness this reduction has to be in polynomial time, and then size matters.

Member since Oct 2016
803 posts

20190112, 08:54 #6
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. 
Member since Jul 2016
91 posts

20190112, 08:58 #7
I get that, but that's not a reduction?

Member since Oct 2016
803 posts

20190112, 09:02 #8
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"... 
Member since Jul 2016
91 posts

20190112, 09:11 #9
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) 1. We get an instance x of SAT 2. We reduce it to a DNF 3. We solve the DNF 4. 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 nontrivial. 
Member since Oct 2016
803 posts

20190112, 09:40 #10
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 
Member since Jul 2016
91 posts

20190112, 09:58 #11
See here why the runtime is exponential https://en.wikipedia.org/wiki/Disjunctive_normal_form#Conv….
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 https://cstheory.stackexchange.com/a/1414 claims it isn't). 
Member since Oct 2016
803 posts

20190112, 10:07 #12
Yes, I know it is Well, not really. But remember: The goal is to show that reducing formulae to DNF is NPhard. The way to go about this is to show that if there WERE a nonNPhard algorithm (i.e. in particular subexponential), 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? 
Member since Jul 2016
91 posts

20190112, 10:14 #13
Oh yeah, I get it now. Thanks for your answers.

Member since Oct 2016
803 posts

20190112, 10:27 #14
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

Member since Jul 2016
91 posts

20190112, 11:38 #15
Okay nvm still unclear: (I hope I'm not a total idiot and overlook something obvious)
You're assuming two different things here. 1. Assuming nonNPhardness means, that there exist problems in NP which cannot be reduced to DNF in polynomial time. Which is not the same as 2. 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 nonNPhardness, 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 nonNPhardness? Because if it were, we could solve SAT in polynomial time!? 
This post was edited on 20190112, 11:57 by Jonas S.

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