Optimal direct sum results for deterministic and randomized decision tree complexity

A Direct Sum Theorem holds in a model of computation, when for every problem solving some k input instances together is k times as expensive as solving one. We show that Direct Sum Theorems hold in the models of deterministic and randomized decision trees for all relations. We also note that a near optimal Direct Sum Theorem holds for quantum decision trees for boolean functions.     

Decision tree approximations of Boolean functions

Decision trees are popular representations of Boolean functions. We show that, given an alternative representation of a Boolean function f, say as a read-once branching program, one can find a decision tree T which approximates f to any desired amount of accuracy. Moreover, the size of the decision tree is at most that of the smallest decision tree which can represent f and this construction can be obtained in quasi-polynomial time. We also extend this result to the case where one has access only to a source of random evaluations of the Boolean function f instead of a complete representation. In this case, we show that a similar approximation can be obtained with any specified amount of confidence (as opposed to the absolute certainty of the former case.) This latter result implies proper PAC-learnability of decision trees under the uniform distribution without using membership queries.     

On P versus NP $ \cap $ co-NP for decision trees and read-once branching programs

It is known that if a Boolean function f in n variables has a DNF and a CNF of size then f also has a (deterministic) decision tree of size exp(O(log n log² N)). We show that this simulation cannot be made polynomial: we exhibit explicit Boolean functions f that require deterministic trees of size exp where N is the total number of monomials in minimal DNFs for f and ?f. Moreover, we exhibit new examples of explicit Boolean functions that require deterministic read-once branching programs of exponential size whereas both the functions and their negations have small nondeterministic read-once branching programs. One example results from the Bruen—Blokhuis bound on the size of nontrivial blocking sets in projective planes: it is remarkably simple and combinatorially clear. Other examples have the additional property that f is in AC⁰. Received: June 5 1997.     

New upper bounds on the Boolean circuit complexity of symmetric functions

In this note, we present improved upper bounds on the circuit complexity of symmetric Boolean functions. In particular, we describe circuits of size 4.5n+o(n) for any symmetric function of n variables, as well as circuits of size 3n for function.     

Unrestricted vs restricted cut in a tableau method for Boolean circuits

This paper studies the relative efficiency of variations of a tableau method for Boolean circuit satisfiability checking. The considered method is a nonclausal generalisation of the Davis–Putnam–Logemann–Loveland (DPLL) procedure to Boolean circuits. The variations are obtained by restricting the use of the cut (splitting) rule in several natural ways. It is shown that the more restricted variations cannot polynomially simulate the less restricted ones. For each pair of methods T, T′, an infinite family of circuits is devised for which T has polynomial size proofs while in T′ the minimal proofs are of exponential size w.r.t. n, implying exponential separation of T and T′ w.r.t. n. The results also apply to DPLL for formulas in conjunctive normal form obtained from Boolean circuits by using Tseitin’s translation. Thus DPLL with the considered cut restrictions, such as allowing splitting only on the variables corresponding to the input gates, cannot polynomially simulate DPLL with unrestricted splitting.AMS subject classification 03B70, 03F20, 68T15, 68T20The financial support from Academy of Finland (project #53695) is gratefully acknowledged.Tommi Junttila: This work was partially done while visiting ITC-IRST (Trento, Italy), and has been sponsored by the CALCULEMUS! IHP-RTN EC project, contract code HPRN-CT-2000-00102.     

马尔可夫决策过程复杂性的熵测度

应用Shannon熵和其他熵指数来度量马尔可夫决策的复杂性．将马尔可夫链的复杂性、不确定性和不可预测性的度量扩展到马尔可夫决策，提出一套基于信息理论的复杂性度量方法，可用于随机和确定性策略下的完全观测和不完全观测马尔可夫决策．对有关数值进行仿真研究，并给出了计算结果．     

基于关联度函数的决策树分类算法

为了克服决策树算法中普遍存在的多值偏向问题,提出了一种新的基于关联度函数的决策树算法--AF算法,并从理论上分析了它克服多值偏向的原理。通过实验发现,与ID3算法比较,AF算法不仅克服了多值偏向问题,而且保持了较高的分类正确率。     

Reflections on “Representations of sets of Boolean functions by commutative rings” by Roman Smolensky

The paper by Roman Smolensky is a nice example of the art of studying mathematical structures that are, on the one hand, motivated by real computational problems but are, on the other hand, not obviously related.Dedicated to the memory of Roman Smolensky     

决策表中粗糙集的布尔矩阵表示

建立了布尔矩阵与逻辑方程组的解和决策表中的属性集之间的关系;然后在此基础上给出了决策表中的粗糙集理论的布尔矩阵表示;最后证明了属性约简在布尔矩阵和代数两种不同表示下是等价的。这些结论有助于人们深刻理解粗糙集理论的本质,同时为寻找高效的属性约简算法奠定了基础。     

Parameterized complexity of basic decision problems for tree automata

There are many decision problems in automata theory (including membership, emptiness, inclusion and universality problems) that are NP-hard for some classes of tree automata (TA). The study of their parameterized complexity allows us to find new bounds of their nonpolynomial time algorithmic behaviours. We present results of such a study for classical TA, rigid tree automata, TA with global equality and disequality and t-DAG automata. As parameters we consider the number of states, the cardinality of the signature, the size of the term or the t-dag and the size of the automaton.     

Bases for Boolean co-clones

The complexity of various problems in connection with Boolean constraints, like, for example, quantified Boolean constraint satisfaction, have been studied recently. Depending on what types of constraints may be used, the complexity of such problems varies. A very interesting observation of the recent past has been that the thus derived classification of constraints can be explained with the help of universal algebra. More precisely, the difficulty of such a constraint problem often depends on the co-clone the constraints are from. A co-clone is a set of Boolean relations that is closed under very natural closure operations. Nearly all these co-clones can be generated by said operators out of a finite set of relations, a so-called base. Knowing a, preferably simple, base for each co-clone can therefore be of great value when studying the complexity of Boolean constraint problems, since this knowledge reduces the infinitely many cases of equivalent problems to a single one—the constraint satisfaction problem for this base. In this paper we give a finite and simple base for every Boolean co-clone, where this is possible. We give evidence that the presented bases are as easy as possible.     

The optimal read-once branching program complexity for the direct storage access function

Branching programs are computation models measuring the space of (Turing machine) computations. Read-once branching programs (BP1s) are the most general model where each graph-theoretical path is the computation path for some input. Exponential lower bounds on the size of read-once branching programs are known since a long time. Nevertheless, there are only few functions where the BP1 size is asymptotically known exactly. In this paper, the exact BP1 size of a fundamental function, the direct storage access function, is determined.     

Probabilistic verification of Boolean functions

We present a novel method for verifying the equivalence of two Boolean functions. Each function is hashed to an integer code by assigning random integer values to the input variables and evaluating an integer-valued transformation of the original function. The hash codes for two equivalent functions are always equal. Thus the equivalence of two functions can be verified with a very low probability of error, which arises from unlikely collisions between inequivalent functions. An upper bound, , on the probability of error is known a priori. The bound can be decreased exponentially by making multiple runs. Results indicate significant time and space advantages for this method over techniques that represent each function as a single OBDD. Some functions known to require space (and time) exponential in the number of input variables for these techniques require only polynomial resources using our method. Experimental results indicate that probabilistic verification can provide an attractive alternative for verifying functions too large to be handled using these OBDD-based techniques.     

A complexity gap for tree resolution

This paper shows that any sequence of tautologies which expresses the validity of a fixed combinatorial principle either is “easy”, i.e. has polynomial size tree-resolution proofs, or is “difficult”, i.e. requires exponential size tree-resolution proofs. It is shown that the class of tautologies which are hard (for tree resolution) is identical to the class of tautologies which are based on combinatorial principles which are violated for infinite sets. Further it is shown that the gap phenomenon is valid for tautologies based on infinite mathematical theories (i.e. not just based on a single proposition).?A corollary to this classification is that it is undecidable whether a sequence has polynomial size tree-resolution proofs or requires exponential size tree-resolution proofs. It also follows that the degree of the polynomial in the polynomial size (in case it exists) is non-recursive, but semi-decidable. Received: November 8, 2000.     

复杂度可伸缩的帧间模式选择

针对H.264/AVC中复杂度无法满足终端设备异构性的问题,提出一种新的帧间模式选择算法。利用相邻宏块的空间相关性和时间相关性,进行模式预测,并通过复杂度伸缩因子,控制参与预测的模式的数目,使复杂度在20%到100%之间灵活变化。实验结果表明,该算法能在视频质量和复杂度之间形成良好的折中,适应从高端设备到低端设备的计算能力差异。     

Partitioning 1-variable Boolean functions for various classification of n-variable Boolean functions

This paper addresses all possible equivalence classes of 1-variable Boolean functions and from these classes using recursion and Cartesian product of sets, 15 different ways of classifications of n-variable Boolean functions are obtained. The properties with regard to the size and the number of classes for these 15 different ways are also elaborated.