(I had been thinking of this for a post then Lance's post on search versus decision inspired me to write up these thoughts.)
When teaching NP-completeness we often say
The problem we really care about is, for example, given a weighted graph and two vertices s and t, find the optimal way to go from s to t while hitting every node. But its cleaner mathematically to look at the decision problem:
{ (G,s,t,C) : there is a Ham Path from s to t that costs \le C }
The search and decision are poly time equivalent, so its fine to just look at the decision. Indeed- if our interest in in lower bounds then clearly if Decision is hard then Find is Hard.
But here are some questions about search vs decision in general, not just with regard to P vs NP.
1) Is there ever a case where the real world actually cares about the decision version? I can think of just one- given a number is it PRIME is used in Crypto. The real world does not need the witness that its prime (or similar). They just want a prime. Any other cases?
2) How far apart can search and decision be? NP-decision and NP-search they are poly equivalent. In other domains can they be very far apart? For example, is FINDING a k-clique or k-ind set in a graph on 2^{2k} vertices require roughly n^k steps (go through all k-sets) or can we do much better? I suspect this is unknown but would be delighted if a commenter tells me otherwise.
I can come up with cases in mathematical biology where you are studying genetic regulatory networks and looking for specific subgraphs that are provably NP, where I wouldn't care really about where the subgraph exists, but simply that it exists, since it's existence tells me a lot about switching pathways for gene expression.
ReplyDeleteIn random CSP (say random $k$-SAT) there is a range of probabilities where we know that with high probability a satisfying assignment exists, but it's generally conjectured that finding one is hard.
ReplyDeleteYour example isn't good, since for the specific numbers you give, just pick a vertex, throw away the smaller of neighbours and non-neighbours, repeat $2k-1$ steps, gives a $k$-clique or $k$-independent set in $O(k2^{2k})$-time. And something like this is true for any number we can prove is at least $R(k)$. (David Conlon's proof, I think, can be made into an algorithm)
But, even if you assume $R(k)\le 3.99^k$, we don't know any algorithm which works fast on a graph with $3.99^k$ vertices.
Hi Bill,
ReplyDeleteHere's a symbol for you to use in your post: ≤
For (2), you must have a typo; you must mean "How far apart ...?"
ReplyDeleteFixed, thanks
DeleteHow about the word problem for a free algebra (NP-complete for inverse rings, for example), polynomial identity testing ((1+x)^n)=1+x^n mod n iff n is prime, for example), or graph isomorphism testing. At least we are normally not interested in the isomorphism itself for graph isomorphism, even so we would prefer to get a canonical labeling instead of just yes/no, so that we can quickly lookup our graph, or throw-out duplicates.
ReplyDeleteYou bring up two good questions, maybe three
ReplyDelete1) are there people in the real world who care about Graph Isom?
2) If so, do they care about the actual isom?
3) ``we are normally not interested in the isom itself'' - who is ``we''
By "we", I just meant the actual applications for which Graph Isom programs like bliss, conauto nauty, saucy, Traces, ... have been used, that "I" was aware of. These are things like explicitly generating all different small instances of some mathematical structures, counting the number of instances of some mathematical structure for given "rather small" parameters limiting the size of the structures, looking up biological or chemical structures in databases, ...
ReplyDeleteBoth wikipedia and MSE try to describe the typical applications of graph isomorphism. I like the perturbative expansion of Feynman's path integral application (since it shows why one wants to list all small instances of some mathematical structure), but I didn't spot a clear application of graph automorphism in those lists yet.
In all those applications, canonization is what one is interested in, instead of an actual isomorphism. But since conauto and saucy only compute the automorphism group without offering canonization functionality, this cannot be the whole truth. I just tried looking at the conauto and saucy home pages to learn more about applications of graph automorphism. Let me just quote from saucy: "Many computational tools have recently begun to benefit from the use of the symmetry inherent in the tasks they solve, and use general-purpose graph symmetry tools to uncover this symmetry. Common applications include organic chemistry, constraint solvers, logistics, optimization, bio-informatics, and finite group theory."
Instead of talking about polynomial identity testing or word problems, it might be simpler to just talk about evaluation of canonical binary relations, like a partial order relation, or some equivalence relation. The decision problem is interesting for those cases, simply because those relations evaluate to true or false (for two given elements).
ReplyDeleteThe canonization is a bit different, since here a deterministic answer is of interest, but the answer is not restricted to true or false. The reduction of a search problem to a decision problem gives us such a deterministic answer, even so a nondeterministic answer would have been perfectly fine for that case. In fact, if we accept this "deterministic answer" property and restrict attention to partial functions, then we just get the PF^NP complexity class (of partial functions), which is not more complicated than the corresponding Δ^NP complexity class (of decision problems). This even gives us a nice example where Cook ("Turing") reductions are more appropriate than Karp ("many-one") reductions.
This also helps to understand the feeling that "its cleaner mathematically to look at the decision problem", since a decision problem always has a deterministic answer, while getting a deterministic answer for a non-deterministic problem (with many valid answers) somehow feels wrong. Contemplating "canonization" can help to appreciate how getting a deterministic answer still fits together with multiple valid answers.
In crypto applications, we care about decisional versions of problems all the time...
ReplyDeleteIn algorithmic graph theory, there are algorithms for solving problems on special graph classes, as bipartite graphs, for example. For using such algorithms in practice one should first check whether the graph indeed belongs to the desired graph class, which is a decision problem.
ReplyDeleteI can also think on problem involving a budget or profit, for which you could solve a decision problem before taking some action. You would only do something if you have enough resources or would get at least some profit from it.