0
$\begingroup$

A boolean expression is valid if it is true for every valuation. The problem $\text{BOOL-VAL}$ asks whether a given boolean expression is valid. As the question suggests I need to show that $\text{BOOL-VAL}$ is decidable in linear time. I have no idea how to go about proving this.

Is $\text{BOOL-VAL}$ the complement of $\text{BOOL-SAT}$?

Moreover, A boolean expression is Disjunctive Normal if it is the disjunction of conjunctive clauses, where a conjunctive clause is the conjunction of 1 or more literals. Such an expression is said to be a DNF (“disjunctive normal formula”). $\text{DNF-SAT}$ says given a DNF, is it satisfiable? The way I want to prove that it is decidable in linear time is like in $\text{CNF-SAT}$ we want atleast one literal per clause to be true and here we want atleast one clause to be true so that somehow intuitevely reduces the number of steps need to come to conclusion leading to lower time complexity but I'm not sure if I'm correct.

Source: This was asked as a brainteaser in my ToC class. There are two questions but I was told that they are basically the same so I asked both.

$\endgroup$
4
  • $\begingroup$ How is the boolean expression provided as input? What's the context where you encountered this? Can you credit the original source? Please ask only one question per post. I encourage you to edit your post based on this feedback. $\endgroup$
    – D.W.
    Commented Dec 10, 2022 at 22:55
  • $\begingroup$ I've made the required changes. $\endgroup$
    – user153634
    Commented Dec 10, 2022 at 23:12
  • 1
    $\begingroup$ I still don't understand how the boolean expression is provided as input. Also, it is two separate questions. Perhaps you might ask one, and then see if the answer to that one helps you figure out the solution to the other. $\endgroup$
    – D.W.
    Commented Dec 10, 2022 at 23:13
  • $\begingroup$ The boolean expression that is provided for boolval is kinda random that is to say it is not in any standard form like CNF or DNF $\endgroup$
    – user153634
    Commented Dec 10, 2022 at 23:33

1 Answer 1

1
$\begingroup$

No. What you are trying to show is not correct. As far as we know, there is no efficient algorithm to test whether an arbitrary boolean expression is valid.

If $\varphi$ is a boolean formula in CNF format, then $\neg \varphi$ is valid iff $\varphi$ is unsatisfiable. So if you had a linear-time algorithm to test for validity, you could apply it to $\neg \varphi$, and thereby learn in linear time whether $\varphi$ is satisfiable. That would constitute an algorithm proving that P=NP. That seems very unlikely, given our current state of knowledge.

Testing whether a CNF formula is valid can be done in linear time ($\varphi$ is valid iff every one of its clauses is valid, and a clause is valid iff <you fill in this part>), but testing whether a DNF formula is valid cannot be done in linear time (or even polynomial time) unless P=NP. Similarly, testing whether a DNF formula is satisfiable can be done in linear time, but testing whether a CNF formula is satisfiable cannot be done in linear time (or even polynomial time) unless P=NP.

$\endgroup$
2
  • $\begingroup$ Can you please elaborate on how testing whether a CNF formula is valid can be done in linear time? $\endgroup$
    – user153634
    Commented Dec 11, 2022 at 22:15
  • $\begingroup$ @OswaldoMobrey, It's a nice exercise. I encourage you to figure out that part on your own. I've already provided a massive hint in the answer. Perhaps it might help you to work through a few examples by hand. $\endgroup$
    – D.W.
    Commented Dec 11, 2022 at 23:47

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.