It seems to me to be incorrect to say that lexicographic DFS is P-complete, since it isn't a decision problem. There is a corresponding decision problem, first DFS ordering, which is known to be P-complete. However, I want to talk about complexity of DFS, not it's decision problem. What complexity class should I say DFS belongs to?
Asked By : Adam Kurkiewicz
Answered By : Luke Mathieson
The formal name for a problem where you want to actually produce the solution as the output (not just say yes or no to whether one exists) is a Function Problem if every input has an associated output, or a Search Problem if some inputs might not have any solution (of course a function problem is just a special case of a search problem).
In this case, every graph has a lexicographic depth first ordering, so for any graph there is some output that can be produced, and you have a function problem. The class of function problems that can be computed in deterministic polynomial time is (cunningly) called FP.
Going out on a limb (with regards to my knowledge, someone else might be able to confirm this), I suspect that the obvious relationship1 between P and FP holds for complete problems too, so your problem should also be FP-complete.
- Note that this relationship normally relies on Turing reductions, but seeing as P=co-P there shouldn't be too much of a problem here.
Best Answer from StackOverflow
Question Source : http://cs.stackexchange.com/questions/21620
0 comments:
Post a Comment
Let us know your responses and feedback