---
tag: PGZ13VYQWN
kind: concept
name: Evasive Boolean function
sources:
  - wikipedia: en:26006899@r1337262166
    locator: Evasive Boolean function
    note: adopted
    mention: wikipedia://en/26006899
    sections: [Summary]
same_as:
  wikidata: Q5416097
  wikipedia: Evasive Boolean function
inventory: [QHZJEPY32S]
---

## Summary

In mathematics, an **evasive Boolean function** $f$ (of $n$ variables) is a [[Boolean function|0A58THH5XV]] for which every decision tree algorithm has running time of exactly $n$. Consequently, every decision tree algorithm that represents the function has, at worst case, a running time of $n$.