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 |