计算机病毒的计算复杂度问题

计算机病毒对计算机系统及软件造成各种各样的损害，除了一些常见的损害，例如删除数据或程序、修改系统信息以外，它们还造成一些非破坏性的影响，例如消耗大量的存贮及时间。这个问题涉及到计算机病毒的计算复杂度。文章初步探讨计算机病毒的计算复杂度问题，从数学上证明两个基本结论：存在计算机病毒，它的传染过程具有任意大计算复杂度；存在计算机病毒，被感染程序的执行过程具有任意大的计算复杂度。除此而外，文章简要讨论计算机病毒检测过程的计算复杂度问题。