布尔函数与计算模型：平行计算复杂性的探索

需积分: 9 70 浏览量更新于2024-07-25 2 收藏 7.02MB PDF 举报

"《Boolean Functions and Computation Models》是由Peter Clote和Evangelos Kranakis合著，Springer出版社于2002年出版的一本理论计算机科学教材。本书全面探讨了布尔函数、电路、并行计算模型、函数代数和证明系统的研究，旨在阐明快速并行计算的结构。书中通过有限组合论、概率论、有限群论、有限模型理论和证明理论等多元技术，强调并行计算的复杂性。同时，它研究了非确定性多项式时间问题的进展以及各种证明系统的复杂性。这本书适合对复杂性理论有深入兴趣的本科高年级学生和研究生，以及相关领域的研究人员。" 本文关键词包括：Beweissysteme（证明系统）、Boolesche Funktionen（布尔函数）、Komplexitätstheorie（复杂性理论）、Parallele Rechnen（并行计算）。相关主题涵盖了数学、软件工程和理论计算机科学。部分内容提到了“Textsin Theoretical Computer Science”系列，由欧洲理论计算机科学协会（EATCS）支持，并有一系列的顾问委员会成员。此外，还介绍了该书的系列编辑，包括Wilfried Brauer、Grzegorz Rozenberg和Arto Salomaa等知名学者。本书深入分析了布尔函数在计算模型中的应用，布尔函数是逻辑运算的基础，它们在电路设计和计算复杂性理论中扮演着核心角色。电路，特别是布尔电路，被用来研究非均匀计算模型的效率，而并行计算模型则探讨了如何在多处理器或分布式环境中高效执行任务。证明系统部分则涉及到了形式验证和计算复杂性的理论方面，这些理论对于理解算法的界限和可计算性问题至关重要。通过对非确定性多项式时间（NP）问题的探讨，本书触及了计算复杂性理论的核心问题之一，即是否存在有效的方法可以解决所有NP问题。同时，不同证明系统的复杂性分析为理解证明的难度和构造提供了理论框架。《Boolean Functions and Computation Models》是一部深入研究计算复杂性和并行计算理论的重要教材，它将帮助读者理解布尔函数如何在各种计算模型中工作，以及如何评估和比较不同计算模型的效率。对于想要在理论计算机科学领域深化知识的学生和研究人员来说，这本书提供了一个宝贵的资源。

1. Boolean Functions and Circuits

Mathematical facts worthy of being studied are those which, by

their analogy with other facts, are capable of conducting us to

the knowledge of a mathematical law, ... H. Poincare [Poi52]

1.1 Introduction

Many fundamental questions in complexity theory can be formulated as a

language recognition problem, where by language L we understand a set of

strings over a finite alphabet, say £' = 10, 11. The basic question is then

to determine the computational resources (such as time, space, number of

processors, energy consumption of a chip, etc.) needed in determining whether

or not x E L, for any string x E Z*. In turn, if for any n we let f,,, denote

the characteristic function of L fl {0,1}n, then the previous question can be

rephrased as a problem of determining the computational resources needed

to compute the boolean function f,, (x), for arbitrary x, n.

There are many natural models for computing a boolean function: boolean

circuits, threshold and modular counting circuits, boolean formula, switch-

ing networks, branching programs, VLSI circuits, etc. In this chapter, we

introduce some elementary concepts concerning boolean functions, formulas

and circuits, then proceed to construct efficient boolean circuits for parsing

and integer arithmetic, and then consider general construction methods for

arbitrary boolean functions.

Apart from the obvious fact that boolean circuits underlie computer hard-

ware, two important justifications for their study are:

1. Boolean circuit families with unbounded fan-in AND/OR gates of certain

size and depth correspond exactly to parallel random access machines

(PRAM) with certain processor and time bounds [SV84]. If one neglects

the complexity induced by message passing, then the virtual machine for

certain massively parallel machines [HS86] is essentially the PRAM. Thus

boolean circuit theory has applications in parallel algorithm design.

2. Boolean circuit lower bounds are intimately related to the P

= NP ques-

tion, for if an NP-complete problem such as satisfiability SAT of boolean

2 1. Boolean Functions and Circuits

formulas can be shown to have superpolynomial lower bound, then deter-

ministic polynomial time P is different from nondeterministic polynomial

time NP.

1.2 Boolean Functions and Formulas

In this section we introduce the notions of DNF, CNF, term, clause, and char-

acterize complete sets of boolean functions.

A boolean function in the variables xl,... , xn is a map f

{0, 1}n -*

{0, 1}. The collection of all n-ary boolean functions is denoted .tan; clearly

I,t3nI=22'.

Some examples of boolean functions include

the 0-ary constant functions 0 and 1,

the unary function

(negation),

the binary functions V (OR), A (AND), G (EXCLUSIVE OR), -+ (implication,

where x ---+ y is defined by -x V y), and = (equivalence, also called bi-

implication).

Frequently, we will use the alternative notation + and for G) and A, re-

spectively. We also use the symbols V, A, ® for the multivariable OR, AND,

EXCLUSIVE OR, respectively. For the EXCLUSIVE OR function we may occa-

sionally use the summation symbol.

A literal is a boolean variable xi or its negation -xi, where the latter is

often denoted Ti. The negation of literal xi is xi. A propositional formula (or

boolean formula over the De Morgan basis {A, V,

0, 1}) is defined recur-

sively as follows:

The constants (i.e., 0-place connectives) 0 (FALSE) and 1 (TRUE) are propo-

sitional formulas.

A boolean variable is a propositional formula.

If F and G are propositional formulas, then -F (negation), (F A G) (con-

junction) and (F V G) (disjunction) are propositional formulas.

The connectives A and V associate to the right, so that F V G V H means

F V (G V H). Let x' =x and x0 = -x. A conjunction of the form x11 A ... A

x'n, where ai E {0, 1}, is called a term

. Dually, a disjunction of the form

x11 V

V xW, where ai E {0, 1}, is called a clause . An s-term (s-clause) is

a term (clause) of at most s literals. A variable xi is said to occur in, or be

mentioned in a term or clause if either xi or Ti appears in the term or clause.

A truth assignment for a boolean formula F with variables x1,... , xn is

a mapping a :

{x1,.

.. , xn} --* {0, 1}. Recall that 0 represents FALSE and

1 represents TRUE. The truth assignment or yields a truth value for F as

defined recursively: a(-G) = 1 - a(G), a(G A H) = min(a(G), a(H)), a(G V

H) = max(a(G), a(H)). If a(F) = 1 (or 0), then or is said to be a satisfying

(falsifying) truth assignment for F, and this is sometimes written a

剩余615页未读，继续阅读

独孤过儿

粉丝: 586
资源: 38

布尔函数与计算模型：平行计算复杂性的探索

Test_sget_boolean.rar_sget-boolean

第三部分：学会在mimics中操作Boolean.avi

boolean.py:在一个模块中实现布尔代数

Python实现布尔代数库：boolean.py介绍

以下哪一个语句不是返回基本类型boolean的true值的。（ ） A、new Boolean("true").booleanValue() B、Boolean.parseBoolean("TRUE") C、 Boolean.parseBoolean("true") D、Boolean.valueOf("true")

boolean.valueof(),和boolean.getboolean的区别

java.lang.NullPointerException: Attempt to invoke virtual method 'boolean java.lang.Boolean.booleanValue()' on a null object reference

boolean.getboolean

.autoCloseStream(Boolean.FALSE)

Boolean.TRUE.equals(redisService.exists(cacheKey))的意义

最新资源

以下哪一个语句不是返回基本类型boolean的true值的。（） A、new Boolean("true").booleanValue() B、Boolean.parseBoolean("TRUE") C、 Boolean.parseBoolean("true") D、Boolean.valueOf("true")