No label defined (Q3334980)
From MaRDI portal
!
This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use the normal view instead:
scientific article; zbMATH DE number 3868606
| Language | Label | Description | Also known as |
|---|---|---|---|
| default for all languages | No label defined |
||
| English | No label defined |
scientific article; zbMATH DE number 3868606 |
Statements
1984
0 references
argument complexity of Boolean functions
0 references
decision trees
0 references
k-transitivity
0 references
Aanderaa-Rosenberg conjecture
0 references
decision algorithm
0 references
exhaustiveness of Boolean functions
0 references
0.9325149
0 references
0.9280865
0 references
0.9151349
0 references
0.9060518
0 references
0.90551186
0 references
0.90551186
0 references
0.8978027
0 references
0.8972492
0 references
[For the entire collection see Zbl 0538.00005.] The argument complexity C(P) of a Boolean function \(P:\{0,1\}^ d\to \{0,1\}\) is the number of components of an input vector x which an optimal decision algorithm for P requires in the worst case to decide whether \(P(x)=1\). If \(C(P)=d\), then P is called exhaustive. It is shown that P is exhaustive, if P is nontrivial and invariant under a k- transitive permutation group acting on the arguments, where \(k>(d/3)+1\) (an immediate consequence is that nontrivial symmetric functions are exhaustive). Under the assumption that there is no 6-transitive group except the symmetric and alternating groups, it is shown that there exists a least universal lower bound \(k_ 0\), \(2\leq k_ 0\leq 6\), \(k_ 0\neq 5\), such that \(k_ 0\)-transivity is sufficient for the exhaustiveness of Boolean functions P with \(P(0...0)\neq P(1...1).\) In addition, it is shown that sharply 2-transitivity implies exhaustiveness. Further investigations in the argument complexity of Boolean functions described by group theoretical properties can be found in the author's dissertation which will appear in 1985, where he also shows that \(k_ 0\neq 6\).
0 references