| Article ID | Journal | Published Year | Pages | File Type |
|---|---|---|---|---|
| 6416976 | Journal of Complexity | 2012 | 8 Pages |
Abstract
We prove the logical independence of a complexity-theoretic and a statistical randomness property of sequences over a finite field. The two properties relate to the linear complexity profile and to the â-distribution of sequences, respectively. The proofs are given by constructing counterexamples to the presumed logical implications between these two properties.
⺠Complexity-theoretic and statistical randomness properties are usually independent. ⺠A good linear complexity profile need not imply an â-distribution. ⺠An â-distribution need not imply a good linear complexity profile.
Related Topics
Physical Sciences and Engineering
Mathematics
Analysis
Authors
Harald Niederreiter,