Are there problems in CS where no efficient algorithms are known, despite existence theorems proving such efficient algorithms must exist?
What are these problems called? Where can I find out more?
3
-
4$\begingroup$ I think this is relevant: en.wikipedia.org/wiki/Minor_(graph_theory)#Algorithms $\endgroup$– user1338Feb 7, 2011 at 20:35
-
3$\begingroup$ What is your question? In the title says "solutions", but in the contents you write "algorithms". $\endgroup$– Marcos VillagraFeb 8, 2011 at 1:35
-
6$\begingroup$ I think it would better if you ask for interesting/natural problems, otherwise it is easy to define such problems: take any mathematical statement that is not known to be true or false, make the problem output 1 (independent of input) if it is true and 0 if it is false. There are two very simple algorithms that one of them solves this problem, but deciding which is basically proving/disproving the mathematical statement, so we don't know which one solves it. $\endgroup$– KavehFeb 8, 2011 at 10:03
Add a comment
|
4 Answers
$\begingroup$
$\endgroup$
0
As an example, Shelby Kimmel uses the adversary method in this paper to show that there has to exist $O(1)$ query algorithm for a certain problem for which we do not know a constant query solution. She does this in a particularly slick way by finding the query complexity of the problem composed with itself $d$ times and then finding the query complexity $Q$ of the composted function, and noting that the query complexity of the original function is order $Q^\frac{1}{d}$.
answered Feb 8, 2011 at 0:37
$\begingroup$
$\endgroup$
Sure, there are lots of examples, at least in the spirit of your question.
Often one gets such a result from the probabilistic method. For example, one paper that I like that runs into the problem is on reconstructing graphs in the additive model. Here, the authors show that there exists a set of $O(dn)$ queries that will (optimally) learn the target graph. Given this set, the algorithm is efficient. However, they use the probabilistic method to show the existence of this small set (for each problem size) that will work on all inputs, but do not explicitly construct it. So the best they can do is just a brute-force search through an exponential family of queries because they don't have an explicit construction.
answered Feb 7, 2011 at 21:56
$\begingroup$
$\endgroup$
9
No, you can always use The fastest and the shortest algorithm for all well-defined problems. ;)
-
$\begingroup$ I wasn't totally serious but observe that Hutter's construction actually proves the algorithm's correctness. Why do you think it does not answer the question? $\endgroup$ Feb 7, 2011 at 22:56
-
4$\begingroup$ @Ross Snider: of course undecidable languages escape Hutter's result: he is, after all, giving an algorithm! However, unlike Levin search, which requires that problem instances have verifiable certificates (like NP search problems), Hutter's search does not. It merely requires that the problem be stated in a formal language, which can serve as the basis for exhaustively searching for proofs [that some TM is in fact solving the specified problem]. Also, Hutter/Levin does not give us existence proofs of efficient algorithms for a problem unless we already know the problem has such an algorithm. $\endgroup$ Feb 8, 2011 at 5:46
-
1$\begingroup$ @Joshua I brought up undecidable languages as an example of something that Hutter/Levin search could not arguably decide (I tried to pick something obvious) but which remains "well-defined"; it is an argument against the claim waged in the title of the paper. Of course, I was careful to admit I hadn't read the contents, which I'll have to do now. $\endgroup$ Feb 8, 2011 at 6:35
-
1$\begingroup$ Is this algorithm the computational content of the equivalence of constructive and classical mathematics on forall-exists statements? $\endgroup$ Feb 8, 2011 at 9:02
-
1$\begingroup$ @Neel Kirshnaswami: It's hard to say, since I didn't know there was such an equivalence! Can you give a pointer? $\endgroup$ Feb 8, 2011 at 15:25
$\begingroup$
$\endgroup$
3
Edit: The answer below is regading the existence of solutions to a given computational problem, not on the existence of algorithms. Initially, I misinterpreted the question.
Answer
There is a complexity class that captures this kind of computational problems. It is known as TFNP. It was defined in this paper:
Nimrod Megiddo and Christos Papadimitriou. On total functions, existence theorems and computational complexity. Theoretical Computer Science 81(2):317-324.
Here you'll find problems like Trichromatic Triangle, for which the existence of a solution is guaranteed by Sperner's Lemma (see the paper for the definition of this problem).
You also have the following paper:
Christos Papadimitriou. On the Complexity of the Parity Argument and Other Inefficient Proofs of Existence. Journal of Computer and Systems Science 48(3), 1990.
In this paper you'll find:
- The $n$-dimensional Sperner's lemma, which is a generalization of Trichromatic Triangle.
- Equilibrium of 2-player games.
- Find a second hamiltonian path on a graph.
The paper has a lot of examples of this type of problems. So I recommend to take a look at it.
-
2$\begingroup$ The question asks not about problems with provably existing solutions for their decision versions but about problems with proved existence of efficient algorithms. These are different things. I agree that at first sight the title can mislead. However, only at first sight. $\endgroup$ Feb 8, 2011 at 9:03
-
$\begingroup$ yes, I agree too. But I was totally mislead by the question. Now in this case, the answer is misleading. What do I do? Do I delete de question? Or edit and put a warning about what exactly is answering? $\endgroup$ Feb 8, 2011 at 12:04
-
$\begingroup$ There are no policies on deleting answers, you can always do what you considered appropriate. Personally I think it is fine to leave your answer here. You can put a statement about which question you are exactly answering. $\endgroup$ Feb 8, 2011 at 16:20