Intereting Posts

Probability that at least K cards will go into a bucket
Conditions for continuous extension of a function on an open set to its closure
Singular points
Does there exist a set of exactly five positive integers such that the sum of any three distinct elements is prime?
relations – examples and counterexamples
If the domain is a compact set, pointwise equicontinuity implies uniform equicontinuity.
$4494410$ and friends
Solving Differential Functional Equation $f(2x)=2f(x)f'(x)$
“Planar” graphs on Möbius strips
Find formula for number of dominated vectors in partial order
Lie derivative of a vector field equals the lie bracket
Closed-form of $\int_0^{\pi/2} \arctan(x)\cot(x)\,dx$
Connections between SDE and PDE
Spectral decomposition of a normal matrix
On the set of the sub-sums of a given series

The first well-known $NPC$ problem is the *Boolean Satisfiability Problem,* which has a proof of being $NPC$ done by Cook (Cook-Levin Theorem).

The problem can easily be described the following way:

In complexity theory, the satisfiability problem (SAT) is a decision problem, whose instance is a Boolean expression written using only AND, OR, NOT, variables, and parentheses. So, we should give an answer ‘yes’ if there is a set of boolean variables which yield ‘TRUE’ for the given for the corresponding expression.

However, I have a question. The wikipedia article states the following:

SAT is easier if the formulas are restricted to those in

disjunctive normal form, that is, they are disjunction (OR) of terms, where each term is a conjunction (AND) of literals (possibly negated variables). Such a formula is indeed satisfiable if and only if at least one of its terms is satisfiable, and a term is satisfiable if and only if it does not contain both x and NOT x for some variable x. This can be checked in polynomial time.

So, basically, if the expression is written in the DNF, this problem is not $NPC$, but simply $P$.

However, as far as I know, there is a $O(p(n))$ algorithm to transform any given boolean expression into DNF and DNF exists for any boolean expression.

**What am I missing or misinterpreting?** There is obviously an error in my logic, because it resulted in making the SAT problem $P$, but not $NP$.

Thank you!

- $\sum_{k=1}^nH_k = (n+1)H_n-n$. Why?
- Decomposition of a primitive regular ideal of a quadratic order
- What is the number of full binary trees of height less than $h$
- I understand what a division ring is, but cannot find any examples. Can anyone give me one?
- Canonical basis of an ideal of a quadratic order
- Union, intersection, set theoretic difference of recursively enumerable sets
- Make this visual derivative of sine more rigorous
- Find numbers in a set whose sum equals x
- Optimal algorithm for finding the odd spheres
- What's the history of the result that $p_{n+1} < p_n^2$, and how difficult is the proof?

Your claim that you can convert an arbitrary formula to DNF in polynomial time is mistaken.

You can convert a boolean formula into DNF, but the resulting formula might be very much larger than the original formula—in fact, exponentially so. Since the conversion algorithm must at the very least write out the resulting DNF formula, its running time must be at least the length of the output, and therefore its worst-case running time must be exponential.

Even if you somehow finesse the issue of writing out the DNF version of the input formula, the algorithm you propose takes a formula of size $x$, converts it into a DNF formula of worst-case size $2^x$, and then calculates satisfiability of the DNF formula in time $P(2^x)$ for some polynomial $P$. This is no better in general than just trying every possible satisfying assignment in the original formula.

The Wikipedia article on “Disjunctive Normal Form” has an example of a formula that explodes when converted to DNF. But it’s an easy example. Consider:

$$(A_1\lor B_1)\land(A_2\lor B_2)\land\cdots\land(A_n\lor B_n)$$

This has length proportional to $n$. But in DNF it turns into:

$$(A_1\land A_2\land\cdots\land A_n)\lor\\

(B_1\land A_2\land\cdots\land A_n) \lor \\

(A_1\land B_2\land\cdots\land A_n) \lor \\

(B_1\land B_2\land\cdots\land A_n) \lor \\

\vdots\\

(B_1\land B_2\land\cdots\land B_n)\hphantom{\lor}

$$

with $2^n$ clauses.

- Number of elements in the quotient ring $\mathbb{Z}/(X^2-3, 2X+4)$
- True/False about ring and integral domain
- Can I conjugate a complex number : $\sqrt{a+ib}$?
- Expressing $\sqrt{7+5\sqrt{2}}$ in the form $x+y\sqrt{2}$
- surjective immersion $\mathbb{R}^2 \to \mathbb{R}^2$ which is not a diffeomorphism
- Find all positive integers $n$ for which $1 + 5a_n.a_{n + 1}$ is a perfect square.
- Inverse Laplace transform of s/s-1
- What does multiplication mean in probability theory?
- Existence of an embedding from the rational numbers to $(0,1)$
- Set of Finite Measure: Uncountable disjoint subsets of non-zero measure
- Tangent space in a point and First Ext group
- Is there some way to simplify $\sum_{i=1}^n \sum_{j\neq i}(\frac{j-1}{2})(\frac{i-1}{2}) $ To obtain a closed form.
- If two normed spaces are Lipschitz equivalent, then one if complete iff the other is
- An elliptic curve for the multigrade $\sum^8 a_n^k = \sum^8 b_n^k$ for $k=1,2,3,4,5,9$?
- Research in differential geometry