[Solved]: How can an algorithm have exponential space complexity but polynomial time complexity?

Problem Detail: 

For enumerating the minimal feedback vertex sets of a graph Schwikowski and Speckenmeyer show an algorithm "GENERATE-MFVS" in their publication "On enumerating all minimal solutions of feedback problems". It is said that it runs in polynomial time but uses exponential space in a dictionary.

insert F_q into Q and into D; while Q is not empty do   remove any set F from Q;   output F;   for each uG-successor F′ of F do     if F′ is not contained in D       insert F′ into D and Q;     fi   od od 

How can this be? Does an exponential number of insert operations to the dictionary not inevitably imply exponential time?

Asked By : Tobias Hermann

Answered By : Winston Ewert

This algorithm doesn't run in polynomial time, it runs with polynomial delay. As the paper notes:

Observe that the number of minimal, and even minimum solutions, can be exponential in the size of the graph; Fig. 1 gives an example. Therefore, the total running time of any enumeration algorithm cannot be expected to be polynomial in the size of the graph.

The paper goes onto explain the concept of polynomial delay,

However, certain enumeration algorithms for other combinatorial problems work with polynomial delay, i.e., the algorithm performs at most a polynomial number of steps before the first and between successive outputs.

What's polynomial isn't the entire runtime of the algorithm, its the time between successive outputs. Since the algorithm can output an exponential number of items, the total run time can quite easily be exponential.

When it comes to memory, the paper states:

Note that memory requirements are polynomial for graphs with a polynomial number of MFVS, but potentially exponential for the general case.

Memory goes exponential if we have an exponential number of outputs. But in that case, there is an exponential amount of time passing to fill up that amount of memory as well.

Put another way, memory is exponential because we are measuring memory usage over the entire enumeration process. Time is polynomial because we are only measuring time between two outputs.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/30346