Not logged in. · Lost password · Register

Page:  1  2  next 
Fredy
Member since Jan 2019
6 posts
Subject: 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).
Jazzpirate
Member since Oct 2016
767 posts
+1 Fredy
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.
Perfectly correct.

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.
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  :blush:
Jonas S
Member since Jul 2016
84 posts
Follow up question: how can we reduce SAT to the DNF-language if every equivalent DNF is exponentially larger?
Jazzpirate
Member since Oct 2016
767 posts
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.
Jonas S
Member since Jul 2016
84 posts
But to show NP-hardness this reduction has to be in polynomial time, and then size matters.
Jazzpirate
Member since Oct 2016
767 posts
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.
Jonas S
Member since Jul 2016
84 posts
I get that, but that's not a reduction?
Jazzpirate
Member since Oct 2016
767 posts
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"...
Jonas S
Member since Jul 2016
84 posts
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?

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.

Btw, I dispute the claim that "every equivalent DNF is exponentially larger" as well ;) depending on what exactly you mean by "EVERY equivalent"...

Poorly worded on my part. There are formulae, for which equivalent DNFs are exponentially larger. But either way it makes the reduction non-trivial.
Jazzpirate
Member since Oct 2016
767 posts
Okay, I've had my cup of coffee now :D

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.
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 :D
Jonas S
Member since Jul 2016
84 posts
In which case you're assuming that step 2 is exponential, correct? Which is of course true[...]

See here why the runtime is exponential https://en.wikipedia.org/wiki/Disjunctive_normal_form#Conv….

, but also basically what you're supposed to show - that you can NOT produce a DNF in polynomial time.

So we should just forget about all the complexity stuff and transform arbitrary formulae to DNFs?

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?

Yes that is true, but that is not easy (if at all possible https://cstheory.stackexchange.com/a/1414 claims it isn't).
Jazzpirate
Member since Oct 2016
767 posts
See here why the runtime is exponential
Yes, I know it is ;)
So we should just forget about all the complexity stuff and transform arbitrary formulae to DNFs?
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?
Jonas S
Member since Jul 2016
84 posts
Oh yeah, I get it now. Thanks for your answers.
Jazzpirate
Member since Oct 2016
767 posts
OK, great :D 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 :/
Jonas S
Member since Jul 2016
84 posts
Okay nvm still unclear: (I hope I'm not a total idiot and overlook something obvious)

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.

You're assuming two different things here.
1.
if there WERE a non-NP-hard algorithm
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
2.
(i.e. in particular sub-exponential)
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!?
This post was edited on 2019-01-12, 11:57 by Jonas S.
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:
Page:  1  2  next 
Go to forum
Datenschutz | Kontakt
Powered by the Unclassified NewsBoard software, 20150713-dev, © 2003-2011 by Yves Goergen