Computational Complexity of Computer Viruses
Z.Y. Zhi · 2005
Computer viruses make various injuries on computer systems or software. Beside some familiar injuries, such as destroying on data or programs, modifying system information, etc., they also take some nondestructive ef- fects such as consuming large amount of storage or time. This problem is pertinent to computational complexity of computer viruses. This paper takes initial step to some issues on computational complexity about computer viruses, and gives mathematical proofs of two basic results, which says that there exist computer viruseswith arbitrary compu- tational complexity in their infecting procedure and computer viruses with arbitrary computational complexity in their executing procedure. Moreover, computational complexity for detecting computer viruses is also discussed briefly.