The Complexity of Finite Functions
Lower bounds on the length of formulas for finite functions are obtained from a generalization of a theorem of Specker. Let f: (0,1,...,d-1) [0,1,...,d-1] be a function which can be represented by a formula of length < c.n. For any m, if n is sufficiently large, there is a restriction f...
| Main Author: | |
|---|---|
| Published: |
2023
|
| Online Access: | https://hdl.handle.net/1721.1/149409 |
| Summary: | Lower bounds on the length of formulas for finite functions are obtained from a generalization of a theorem of Specker. Let f: (0,1,...,d-1) [0,1,...,d-1] be a function which can be represented by a formula of length < c.n. For any m, if n is sufficiently large, there is a restriction f': {0,1,...,d-1}m > {0,...,d-1} of f which, is representable by special class of formulas called homogeneous e-complexes. |
|---|