Not logged in. · Lost password · Register

Page:  previous  1  2 
Fredy
Member since Jan 2019
6 posts
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 NP-hard, which probably isn't the ideal solution but I think it works.
Jonas S
Member since Jul 2016
84 posts
is then make an algorithm that decides satisfiability by converting to DNFs first,
but how do you do that in polynomial time?
Fredy
Member since Jan 2019
6 posts
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.
Jonas S
Member since Jul 2016
84 posts
you cannot do it in polynomial time, i.e. it is at least NP-hard.

Those two statements contradict each other.

Also:
you cannot do it in polynomial time,[...] standard way of showing this is through polynomial time reductions[...]
Jazzpirate
Member since Oct 2016
767 posts
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:
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.
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?
Fredy
Member since Jan 2019
6 posts
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/Polynomial-time_reduction#Ma…
Jazzpirate
Member since Oct 2016
767 posts
Note that the reduction function does NOT solve the underlying problem, but only converts inputs from one problem to the other.
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?
Fredy
Member since Jan 2019
6 posts
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 2019-01-12, 13:10 by Fredy.
Jazzpirate
Member since Oct 2016
767 posts
OK, then we're on the same page, thank you :)

This focus on decision problems is exactly what makes this assignment a bit confusing
Yes, that's why I tried to direct the focus away from framing this as a 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
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.
Jonas S
Member since Jul 2016
84 posts
In reply to post #21
Quote by Fredy:
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).

What do you mean by "inputs"?
Jazzpirate
Member since Oct 2016
767 posts
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.
rappatoni
Member since Nov 2018
25 posts
+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 (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.)

1. Search Problems vs Decision Problems

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).

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 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).


2.
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.

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: https://cstheory.stackexchange.com/questions/19434/is-dnf-…). 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).

3. NP and exponential time

(i.e. in particular sub-exponential)
The latter statement is the assumption that DNF is in P.

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.
This post was edited on 2019-01-14, 12:59 by rappatoni.
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:  previous  1  2 
Go to forum
Datenschutz | Kontakt
Powered by the Unclassified NewsBoard software, 20150713-dev, © 2003-2011 by Yves Goergen