Аннотация: Appendix A. Reduction Construction and Proof of the Main Theorem Let = { 1 , … , } be a set of Boolean variables taking Boolean values {+, -}.A triple ( , , ) with , , ∈ {+, -} is called a clause.Let = { 1 , … , } be a set of clauses.Write ( = ) to mean = for = 1, … , .An assignment ( = ) satisfies a clause = ( , , ) if ( , , ) ≠ ( , , ).The 3-SAT problem is: given a set of variables and clauses, decide whether there exists an assignment that satisfies all clauses.We will assume that each variable occurs (negated or not) in at least one clause.In this section, we reduce a 3-SAT instance to an instance of (2) by constructing an appropriate time machine. Construction of the Time MachineLet = + 2 and = 1.Consider a time machine with = 3 + + 3 states and = 7 + 2 transition matrices.Index these states as follows: For each of the variables ∈ , there are states x, x -, and x + .For each of the clauses ∈ , there is a state c.Finally, the last three states are the start state s, the "death" state d, and the "tally" state f.We identify each state with its characteristic (row) vector and define each transition matrix by its action on these basis vectors.If = ( , , ) ∈ , then for each choice of ( , , ) ∈ {+, -} 3 ∖ {( , , )}, define a transition matrix = ,, as follows: z =
Год издания: 2017
Издательство: American Mathematical Society
Источник: Notices of the American Mathematical Society
Ключевые слова: Mathematics and Applications, Computational Geometry and Mesh Generation
Открытый доступ: bronze
Том: 64
Выпуск: 10
Страницы: 1143–1144
