The curse of constructive mathematics -Can the gadget computer go beyond the NP problem?-

KYUMA, Eido

                      kyuma@dpc.aichi-gakuin.ac.jp

General Education, Aichi-gakuin University

1 Introduction

Most computer scientists believe that normal computers work in constructive mathematics. In constructive mathematics, “there exists something” means “we can construct something” or “we know the position of something”, and usual algorithms of most computers work in this way.

Now, I think about the “P = NP ” problem. The P problems and the NP problems are decision problems.

When we solve a decision problem, we have only to get either a ‘yes’ answer or a ‘no’ answer. However, before we know a ‘yes’-‘no’ answer, we get more information from constructive mathematics.

My main question is if there exists an algorithm which gets a ‘yes’-‘no’ answer before we get more information. I think that most computers have the curse of constructive mathematics, and I doubt whether such a thing is possible using algorithms of normal computers.

In this paper, we try to compute an NP problem by using concrete objects, which is called “gadgets”. In the gadget world, it seems that “there exists something” dose not necessarily mean “we can con-

struct something” or “we know the position of something.”

For example, let’s think about the existence of a hole in a sheet. In constructive mathematics, “there exists the hole” means “we know the position of the hole correctly.” However, in the gadget world, if we want to know the existence of the hole, it is sufficient to illuminate this sheet. We do not have to know the position of the hole beforehand.

In this case, it seems that we can know the existence of the hole before we measure the position. This paper discusses the time complexity between these algorithms.

2 Basic Notation

In this paper, we think about the satisfiability of the conjunctive normal form, which is called SAT.

Definition 1. Let n be a natural number. Let U_{n} = {x_{1}, x_{2}, …, x_{n}} be a set of n boolean variables.

Definition 2. Let k be a natural number, and each l_{i} (i = 1, 2, …, k) be either a boolean variable or a negated boolean variable in U_{n}. Then,

l_{1} ∨ l_{2} ∨ ⋯ ∨ l_{k}

is said to be the clause.

Definition 3. Let m be a natural number, and each C_{j} (j = 1, 2, …, m) be a clause. Then,

C_{1} ∧ C_{2} ∧ ⋯ ∧ C_{m}

is said to be the conjunctive normal form.

Definition 4. Let D be the conjunctive normal form w.r.t. U_{n} . If there exists the assignment f : U_{n} → {True, False} such that the value of D is True by substituting the assignment f into variables, then D is satisfied.

Example 5. We use U_{4} = {x_{1}, x_{2}, x_{3}, x_{4}}.

D = \begin{aligned}& ( & x_{1} & ∨ & ¬x_{2} & & & & & ) \\ ∧ & ( & & & x_{2} & ∨ & ¬x_{3} & & & ) \\ ∧ & ( & x_{1} & ∨ & x_{2} & ∨ & x_{3} & & & ) \\ ∧ & & & & ¬x_{2} \\ ∧ & ( & ¬x_{1} & ∨ & x_{2} & ∨ & x_{3} & ∨ & x_{4} & ) \end{aligned}

is the conjunctive normal form. And, there exists the assignment

f(x) = \{ \begin{matrix}True & if x = x_{1}, x_{4} \\ False & if x = x_{2}, x_{3} \end{matrix}

such that the value of D is True by the substitution f. Therefore, D is satisfied.

We fix the number n of variables. And N is the set of all natural numbers. Definition 6. \overline{U_{n}} is defined as the set \{i ∈ N | 1 ≤ i ≤ 2^{n} \}. Definition 7. Let x_{i} be the element of U_{n}. Then, x̃_{i} is defined as

\{ j ∈ \overline{U_{n}} | ∃u, v, w ∈ N ( \begin{matrix}(j = u + v × w) ∧ (1 ≤ u ≤ 2^{n−i}) \\ ∧ (1 ≤ v ≤ 2^{i−1}) ∧ (w = 2^{n−i+1}) \end{matrix} ) \} .

And, ˜¬x_{i} is defined as the set \overline{U_{n}} − x̃_{i} . Example 8. Let n be 4 . Then,

\overline{U_{4}} = \{ 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16 \} ,
x̃_{1} = { 1, 2, 3, 4, 5, 6, 7, 8  } ,
˜¬x_{1} = {  9, 10, 11, 12, 13, 14, 15, 16 } ,
x̃_{2} = { 1, 2, 3, 4,  9, 10, 11, 12  } ,
˜¬x_{2} = {  5, 6, 7, 8,  13, 14, 15, 16 } ,
x̃_{3} = { 1, 2,  5, 6,  9, 10,  13, 14  } ,
˜¬x_{3} = {  3, 4,  7, 8,  11, 12,  15, 16 } .

Exercise 9. Let n be 4 . Then, what are x̃_{4} and ˜¬x_{4}? Definition 10. Let C be the clause (l_{1} ∨ l_{2} ∨ ⋯ ∨ l_{k}) . Then, \overline{C} is defined as

\overline{U_{n}} − l̃_{1} − l̃_{2} − ⋯ − l̃_{k} .

Example 11. Let n be 4, and C be the clause (¬x_{1} ∨ x_{2} ∨ x_{3}) . Then,

\begin{aligned}\overline{C} & = & \overline{U_{4}} − ˜¬x_{1} − x̃_{2} − x̃_{3} \\ & = & \{7, 8\} . \end{aligned}

Definition 12. Let D be the conjunctive normal form (C_{1} ∧ C_{2} ∧ … ∧ C_{m}) . Then, \overline{D} is defined as

\overline{C_{1}} ∪ \overline{C_{2}} ∪ ⋯ ∪ \overline{C_{m}} .

Theorem 13. Let D be the conjunctive normal form. Then, \overline{D} ⫋ \overline{U_{n}} if and only if D is satisfied. Proof. We use the function

g(x) = \{ \begin{matrix}0 & if x = True, \\ 1 & if x = False. \end{matrix}

For each assignment f : \overline{U_{n}} → \{True, False\},

∑_{i=1}^{n} g ( f (x_{i}) ) × 2^{n−i} ∈ \overline{U_{n}} − \overline{D} ↔ D is True by substituting f.

3 The Gadget Computer

First, we fix the conjunctive normal form D = (C_{1} ∧ C_{2} ∧ … ∧ C_{m}) w.r.t. U_{n} .

In this section, we calculate the satisfiability of the conjunctive normal form in the gadget computer. We use m pieces of sheets, whose figures are rectangles 2 height and 2^{n} wide, as gadgets.

Each clause C_{j} correspond to the j-th sheet. And each sheet is in a coordinate plane, such that

{(x, y) ∈ R × R | 0 ≤ x ≤ 2^{n}, 0 ≤ y ≤ 2 } .

Lemma 14. We can make these sheets, and the number of steps in this process is O(m × n) .

Proof. We can measure the length 2^{n} by the n-th folded sheet.

Definition 15. Let l be either a boolean variable or a negated boolean variable in U_{n}. Then, l̂ is defined as

{(x, y) ∈ R × R | ∃ i ∈ l̃ (i − 1 < x < i) , 0 ≤ y < 1 } .

Definition 16. Let C_{j} be the clause l_{1} ∨ l_{2} ∨ ⋯ ∨ l_{k} . Then, Ĉ_{j} is defined as the remainder, such that we cut off parts l_{1}, l_{2}, …, l_{k} from the j-th sheet.

Lemma 17. The number of steps in this cutting process is O(k × n) .

Proof. If we fold this sheet O(n)-times and cut twice well, then we can cut off the part l̂from the sheet. Of course, if n is sufficiently large, then it is physically impossible. However, now we think about the ideal gadget.

Theorem 18. Now, we lay m pieces of cut sheets Ĉ_{1}, Ĉ_{2}, …, Ĉ_{m} one on top of another. Then, we can find the hole in the area {(x, y) ∈ R × R | 0 ≤ x ≤ 2^{n}, 0 ≤ y ≤ 2} , if and only if D is satisfied.

Proof. It is obvious by Theorem 13.

Theorem 19. Using the gadget computer, we can compute the satisfiability of the conjunctive normal form, and the number of steps in this process is the polynomial function of n .

Proof. It is obvious by above Lemmata and Theorem.

4 Conclusion

Using the above algorithm of the gadget computer, it seems that we can know a ‘yes’-‘no’ answer before we get more information. However, I can not prove that it is true at present.

Now, we think about the relation of the time complexity between these algorithms.

Theorem 20. We assume that, for any conjunctive normal form D w.r.t. U_{n} , we compute the satisfiability problem of D O (p (n))-times . If this problem of D has a ‘yes’ answer, then we can get the satisfied assignment f O (n × p (n))-times.

Proof. If D is the conjunctive normal form w.r.t. U_{n} , then the substitute D[x_{i} := True] and D[x_{i} := False] are conjunctive normal forms w.r.t. U_{n} also.

We use the next algorithm.

E := D

for i := 1 to n

if E[x_{i} := True] is satisfied then f(x_{i}) := True and E := E[x_{i} := True]

else f(x_{i}) := False and E := E[x_{i} := False]

next i

If the satisfiability problem of D has a ‘yes’ answer, then we can get the satisfied assignment f using this algorithm.

This result is not good for my project. Because, even if there exists an algorithm which gets a ‘yes’- ‘no’ answer before we get more information, we can get more information almost at the same time by using the algorithm of the same process.

By this thing, I doubts whether it is essential that the NP problem must be a decision problem in the P = NP problem.