THE BOOLEAN FUNCTION WIZARD 1.0 by Scott Aaronson 8/31/2000 INTRODUCTION The Boolean Function Wizard (BFW) is a library to compute properties of Boolean functions. Most (though not all) of the properties are related to decision tree complexity. The original purpose of the BFW was to help investigate open questions in complexity theory, but the library can be used for other purposes as well. INCLUDED FILES WARNING -- The timer code is not ANSI C, so you may need to #undef TIMING (in props.h) to get the code to compile. All .c and .h files are in the /src directory. For the BFW: basic.c Basic properties comput.c Computational complexity properties degree.c Degree properties determin.c Deterministic query complexity properties f.c Command-line interface props.h Header file quantum.c Quantum query complexity properties random.c Randomized query complexity properties sensitiv.c Sensitivity-related properties util.c Utility functions For the lp_solve library (the things you need to link with): debug.c hash.c lpkit.c lpkit.h lptab.c presolve.c read.c readmps.c solve.c Documentation: readme.txt This file Miscellaneous utilities: allf.c Finds all Boolean functions of a given size up to isomorphism .bf files (in /bf directory): xor2.bf 2-variable XOR and2.bf 2-variable AND rand1.bf to rand15.bf Random Boolean functions (uniform distribution) 3-1.bf to 3-10.bf All 3-variable functions up to isomorphism 4-1.bf to 4-208.bf All 4-variable functions up to isomorphism .ini files (in /ini directory): f.ini Default initialization file Many others Can be used as needed (also it's extremely easy to create your own) STRUCTURE The BFW comprises about 4,400 lines of C code (at last count). The core of the library is a struct called "function," which stores a Boolean function's truth table plus lots of auxiliary information about the function that is computed by various routines. To get an idea of the layout of "function," read the comments in props.h. Each Boolean function property in the library has its own C function to compute it. The function takes a "function" struct as input, and returns the property value as output. The function also does some other things: * It starts a timer, which is used to measure how long the algorithm takes. * It sets the prev field of the "function" struct to a numeric code specific to the property. This notifies other routines which was the last property computed. * If a flag is set, it checks to see whether an answer is already cached in the "function" struct, and if so returns that answer without recomputing it. * If a flag is set, it caches its answer in the "function" struct. * If a flag is set, it prints detailed data to the file x.dat, where x.bf is the input file. For example, x.dat contains an optimal decision tree itself, whereas the function's output is just the tree's height. But beware: if you're not familiar with the source code, x.dat will probably look like junk. f.c contains a small command-line interface for the library. Alternatively, you can link to the library by linking with all object files except for f.obj, and by putting an #include "props.h" in your program. Some other notes: the freeware linear programming solver lp_solve 2.3, available at ftp://ftp.es.ele.tue.nl/pub/lp_solve/, is an essential component. Source files for lp_solve are included with the distribution of the BFW. The file util.c contains numerous utility functions (and more under construction), including the functions to create, copy, and destroy "function" structs, and the functions that handle input and output of "function" structs. SUPPORTED PROPERTIES For definitions of these properties and references to the literature, see the paper "Algorithms for Boolean Function Query Measures" by Scott Aaronson. For more detailed definitions (i.e. how non-total functions are handled), see the comments in the source code. All average-case properties are with reference to the uniform distribution. Check the source code to see which properties are currently implemented. BASIC PROPERTIES unate Unateness [isomorphism to a monotone function] qsym Quasisymmetry [isomorphism to a symmetric function] bal Whether f is balanced vars Dependence prime Primality SENSITIVITY-RELATED PROPERTIES s Sensitivity su Sensitivity (average) bs Block sensitivity bsu Block sensitivity (average) es Everywhere sensitivity esu Everywhere sensitivity (average) Amb Ambainis complexity [a lower bound for Q2(f)] inf Maximum influence [of any variable of f] DEGREE AS A POLYNOMIAL deg Degree as a real polynomial (exact) degZ2 Degree as a polynomial over Z[2] deg2 Degree as a real polynomial (2-sided error) ndeg Degree as a real polynomial (nondeterministic, 1-sided) deg1 Degree as a real polynomial (1-sided-error) degs Degree as a real polynomial (nondeterministic, strong) degw Degree as a real polynomial (nondeterministic, weak) DETERMINISTIC QUERY COMPLEXITY D Deterministic query complexity (worst-case) Du Deterministic query complexity (average-case) C Certificate complexity Cu Certificate complexity (average) RANDOMIZED QUERY COMPLEXITY R0 Randomized query complexity (0-error, worst-case) R1 Randomized query complexity (1-sided-error, worst-case) R1u Randomized query complexity (1-sided-error, average-case) R2 Randomized query complexity (2-sided-error, worst-case) R2u Randomized query complexity (2-sided-error, average-case) NR Randomized query complexity (nondeterministic, 1-sided, worst-case) NRu Randomized query complexity (nondet, 1-sided, average-case) NRs Randomized query complexity (nondet, strong, worst-case) NRsu Randomized query complexity (nondet, 1-sided, average-case) NRw Randomized query complexity (nondet, weak, worst-case) NRwu Randomized query complexity (nondet, 1-sided, average-case) QUANTUM QUERY COMPLEXITY QE Quantum query complexity (exact, worst-case) QEu Quantum query complexity (exact, average-case) Q0 Quantum query complexity (zero-error, worst-case) Q0u Quantum query complexity (zero-error, average-case) Q1 Quantum query complexity (1-sided-error, worst-case) Q1u Quantum query complexity (1-sided-error, average-case) Q2 Quantum query complexity (2-sided-error, worst-case) Q2u Quantum query complexity (2-sided-error, average-case) NQ Quantum query complexity (nondeterministic, 1-sided, worst-case) NQu Quantum query complexity (nondet, 1-sided, average-case) NQs Quantum query complexity (nondet, strong, worst-case) NQsu Quantum query complexity (nondet, strong, average-case) NQw Quantum query complexity (nondet, weak, worst-case) NQwu Quantum query complexity (nondet, weak, average-case) EXECUTION f.exe is invoked on the command line with the syntax f [ini_file] is the name of a file containing a Boolean function's truth table. An extension of .bf is automatically appended to the file name. Here is an example of a .bf file, xor2.bf: 2 00 0 01 1 10 1 11 0 The number on top (which is mandatory) is the number of input variables. What follows is the truth table for a function (in this case the XOR function), with one entry per line. The input strings are optional; it would also work to write 2 0 1 1 0 If a Boolean function is partial, use -1 to specify that the function is undefined on a particular input. If a .bf file causes an error, the problem is probably that the file doesn't have Windows-style carriage returns. [ini_file] is the name of an initialization file containing a list of properties to compute, one per line. An extension of .ini is automatically appended to the file name. If [ini_file] is left out, f.ini is used as a default. Here is f.ini: unate qsym vars D C bs es s deg degZ2 deg2 degs ndeg R0 R2 prime Finally, here is an example run: > f xor2 Boolean Function Wizard by Scott Aaronson unate(f) 0 0.000 sec qsym(f) 1 0.000 sec Preprocessing 0.000 sec vars(f) 2 0.000 sec D(f) 2 0.000 sec C(f) 2 0.000 sec bs(f) 2 0.000 sec es(f) 2 0.000 sec s(f) 2 0.000 sec deg(f) 2 0.000 sec degZ2(f) 1 0.000 sec deg2(f) 2 0.030 sec degs(f) 2 0.020 sec ndeg(f) 2 0.030 sec R0(f) 2.000000 0.010 sec 3R2(f) 2.000000 0.000 sec prime(f) 1 0.000 sec