3 ms·
Each VM does some work. If the number of VMs grow exponentially, the work grows exponentially. !=P.
by Deestan 16y ago
Each VM does some work. If the number of VMs grow exponentially, the work grows exponentially. !=P.
- suppressingfire 16y agoBut the getacoder poster only specified that it had to be done in polynomial time, and didn't clarify whether that had to be total CPU time (i.e., "work") or wall clock time. Given that underspecification, it's perfectly justifiable to use an exponential amount of resources to achieve the goal.