2
$\begingroup$

I had a test that I failed to pass, and it had a question that I failed to do.

This is the question:

Let us look at the language TAUTOLOGY: Collect all the phrases $\varphi$ so that each placement on the variables $\varphi$ will provide $\varphi$. We will denote the number of variables in n and the number of phrases in m. Determine which of the following statements is correct:

  1. The language is in $P$
  2. The language is in $NP$ but not in $NPC$.
  3. The language is in $CoNPC$, since $SAT \in NPC$
  4. None of the above claims are true.

I think the correct answer is 3, it makes sense, because it's a complementary language to SAT, but I do not know how to explain it.

1 does not seem right, 2 this is an illogical claim at all - If the language is in NP then it must also be in NPC in my opinion , probably the answer is 3 but I do not know why.

$\endgroup$
2
+50
$\begingroup$

While @nir shahar's answer is not wrong, your question is about the complexity of TAUTOLOGY when we have no assumptions on the structure of the formula. In the special case of Conjunctive Normal Form (CNF, a AND of OR clauses), you can solve TAUTOLOGY in polynomial time, as Shahar says. However, there are other special cases for which TAUTOLOGY is co-NP-complete. This, of course, implies that TAUTOLOGY also in the general case is co-NP-complete.

If you switch the AND's and OR's in some CNF formula $\varphi$, you get a new formula $\varphi'$ that is in Disjunctive Normal Form (DNF). It is not hard to see that some truth assignment makes $\varphi$ true if and only the "opposite" (i.e. make true variables false and vice versa) truth assignment makes $\varphi'$ false. This means that we have a reduction from SATISFIABILITY on CNF formulae to the "FALSIFIABILITY" problem on DNF formulae. Thus, the latter problem is NP-complete.

As TAUTOLOGY ("does every truth assignment make this formula true?") is the complementary problem to FALSIFIABILITY ("does some truth assignment make this formula false?"), TAUTOLOGY on DNF formulae must be co-NP-complete.

$\endgroup$
2
  • $\begingroup$ Thanks for the answer, what is the FALSIFIABILITY problem? I am familiar with the FALSE problem, which belongs to CoNP. Is this the same problem? $\endgroup$
    – dust
    Jul 26 at 12:30
  • 1
    $\begingroup$ It is just the opposite problem of SATISFIABILITY: finding out if some truth assignment makes the given formula false. And just like SAT, it is in NP and NP- complete, as I explained in my answer. $\endgroup$
    – Highheath
    Jul 26 at 12:59
5
$\begingroup$

The main "key" here is to understand how a formula is structured. Assuming the formulas of TAUTOLOGY are in CNF, then there exists a polynomial algorithm:

Let $\varphi=\bigwedge_{i=1}^{k}\limits C_i$ where each $C_i$ is described as an $\lor$ of multiple literals.

Notice, that in order for an assignment $\rho$ to satisfy $\varphi$, we need $\rho$ to satisfy all of the $C_i$'s. Therefore, $\varphi$ is a tautology if and only if all $C_i$'s are tautologies. Since $C_i$ is described as a simple $\lor$ of multiple literals, its easy to check that it is a tautology (check to see if there is a literal and its negation. If there is, its a tautology. Otherwise, it isn't)

Thus, the algorithm will check that each of the clauses $C_i$ is a tautology and will accept only if all of them are tautologies.


Here is a more detailed explanation of the algorithm. First, lets write the algorithm as pseudocode:

The algorithm

  1. Given $\varphi$, decompose it into $C_i$'s such that $\varphi = \bigwedge\limits_{i=1}^k C_i$.
  2. For each $1\le i\le k$, do the following:
    • Decompose $C_i$ into $C_i=l_{i,1}\lor l_{i,2}\lor\dots\lor l_{i,m}$ where all $l_{i,j}$'s are literals.
    • If there are some $j_1,j_2$ such that $l_{i,j_1}=\overline{l_{i,j_2}}$, mark $C_i$ as a tautology
  3. If all $C_i$'s were marked as tautologies, accept. Otherwise, reject.

Complexity

Clearly, the algorithm runs in polynomial time. It has a few nested loops, but thats it. Each loop can add a factor of $n$ into the running time, and hence the run-time is at most $n^c$ for some constant $c$ (in fact, it runs in $n^3$ if it is well-implemented).

Correctness

We want to show that $\varphi\in TAUTOLOGY \iff A(\varphi)=true$ where $A$ is the algorithm described above.

We will start by showing that $\varphi\in TAUTOLOGY \implies A(\varphi)=true$. Indeed, $\varphi$ is satisfied by any assignment. In particular, since $\varphi=\bigwedge \limits_{i=1}^k C_i$, then for any assignment, $\varphi$ is satisfied only if all $C_i$'s are satisfied, and since $\varphi\in TAUTOLOGY$ then we must have that $C_i$ is a tautology as well, for all $i$.

Now, we want to show that all $C_i$'s will be "marked". That is, for every $i$, there is some literal $l_{i,j}$ and its negation in $C_i$. Let us, assume towards contradiction that this isn't the case. Then, we know that all literals $l_{i,j}$ in $C_i$ have to be with some unique variable $x_{i,j}$ (within $C_i$ only. This variable can be used in some other clause $C_{i'}$, but we aren't concerned with that). Let us define the following assignment $\rho$:

$$\rho(x_{i,j}):=\begin{cases}False&l_{i,j}="x_{i,j}"\\True&l_{i,j}="\overline{x_{i,j}}"\end{cases}$$

In this way, we know that for any $j$, the assignment of $\rho$ for $x_{i,j}$ is guaranteed to make $l_{i,j}$ be assigned with $False$. Note, that since all $l_{i,j}$ use some distinct variable $x_{i,j}$, this assignment $\rho$ is well-defined.

But, this means that under the assignment given by $\rho$, $C_i$ gets the value $False$. Now, this means that $\varphi = \bigwedge\limits_{i=1}^k C_i$ also gets the value $False$, in contradiction that any assignment on it must satisfy it, and hence must result in a $True$.

Therefore, we conclude that $C_i$ has to be "marked", for all $i$, and therefore $A(\varphi)=True$ from the definition of the algorithm.

Showing the direction $A(\varphi)=True\implies \varphi\in TAUTOLOGY$ is a very similar process to the above proof.

$\endgroup$
11
  • $\begingroup$ Thanks for the help, I did not understand what the final answer is, I was wrong in my answer? If there is a simple guessing algorithm does that mean the answer is in NP or CoNP? $\endgroup$
    – dust
    Jul 21 at 14:31
  • 2
    $\begingroup$ The answer is in $P$. Its wrong to say "it is similar to the complement of $SAT$ so it must be $coNPC$" $\endgroup$
    – nir shahar
    Jul 21 at 14:38
  • 1
    $\begingroup$ By a deterministic polynomial algorithm $\endgroup$
    – nir shahar
    Jul 21 at 16:24
  • 1
    $\begingroup$ To check if $C_i$ is a tautology its enough to check if it has a literal and its negation. If it has, then any assignment will satisfy it. If it doesn't have, you can easily construct an assignment that wont be satisfied. $\endgroup$
    – nir shahar
    Jul 23 at 21:20
  • 1
    $\begingroup$ @dustyeav I have added a more detailed explanation about the algorithm, its complexity, and its correctness. You can take a look if you want to. $\endgroup$
    – nir shahar
    Jul 24 at 17:44

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.