<p>Sure, there are lots of examples, at least in the spirit of your question.</p>

<p>Often one gets such a result from the <a href="http://en.wikipedia.org/wiki/Probabilistic_method">probabilistic method</a>. For example, one paper that I like that runs into the problem is on <a href="http://hal.archives-ouvertes.fr/docs/00/07/35/17/PDF/RR-3171.pdf">reconstructing graphs in the additive model</a>.  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.</p>

CC BY-SA 2.5
2011-02-07T21:56:00.157Z
2011-02-07T21:56:00.157Z
Lev Reyzin
<p>No, you can always use <a href="http://www.hutter1.net/ai/pfastprg.htm" rel="nofollow">The fastest and the shortest algorithm for all well-defined problems</a>. ;)</p>

CC BY-SA 2.5
2011-02-07T22:56:19.923Z
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?
Marcus Ritt
CC BY-SA 2.5
2011-02-08T01:15:19.767Z
@Marcus Levin search requires the language in question to have a certificate. So at least those infinitely numerous "well defined" undecideable languages like EQUAL_TM escape Hutter-like Turing machine enumerating approaches. At the same time we know that any two TMs will accept the same language or not. (Note: I haven't read the paper in question and suspect he defines "well-defined" to mean 'has a certificate')
Ross Snider
CC BY-SA 2.5
2011-02-08T01:28:12.860Z
It should be added that in context of this question I think that Levin search is, in fact, a valid thing to discuss. So the comment above discussing Levin search and certificates isn't a criticism of this answer to this question. In fact I have upvoted it.
Ross Snider
CC BY-SA 2.5
2011-02-08T05:46:31.277Z
@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.
Joshua Grochow
CC BY-SA 2.5
2011-02-08T06:20:05.270Z
@Joshua Thank you Joshua. I'll have to delve through the Hutter paper, seeing how it doesn't appear to directly be a vanilla Levin search. I'm particularly interested in the following sentence of the abstract: "M avoids Blum's speed-up theorem by ignoring programs without correctness proof."
Ross Snider
CC BY-SA 2.5
2011-02-08T06:35:05.400Z
@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.
Ross Snider
CC BY-SA 2.5
2011-02-08T09:02:51.247Z
Is this algorithm the computational content of the equivalence of constructive and classical mathematics on forall-exists statements?
Neel Krishnaswami
CC BY-SA 2.5
2011-02-08T15:12:00.767Z
@Ross: wrt EQUAL_TM: yes, I should have argued the other way round: if we have an existence proof of an efficient algorithm as the question requires, then Hutter's search is an efficient algorithm. (With the possible exception that the time to compute the algorithm's time bound, Hutter $d_P\,\mathit{time}_{t_P}(x)$ term, makes it inefficient. I don't know if there's such an algorithm.)
Marcus Ritt
CC BY-SA 2.5
2011-02-08T15:25:30.060Z
@Neel Kirshnaswami: It's hard to say, since I didn't know there was such an equivalence! Can you give a pointer?
Joshua Grochow
CC BY-SA 2.5
2011-02-07T22:00:59.033Z
2011-02-07T22:00:59.033Z
Marcus Ritt
<p><strong>Edit:</strong> 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.</p>

<p><strong>Answer</strong></p>

<p>There is a complexity class that captures this kind of computational problems. It is known as <a href="http://qwiki.stanford.edu/index.php/Complexity_Zoo%3aT#tfnp" rel="nofollow">TFNP</a>. It was defined in this paper:</p>

<p><em>Nimrod Megiddo and Christos Papadimitriou. <a href="http://theory.stanford.edu/~megiddo/pdf/papadimX.pdf" rel="nofollow">On total functions, existence theorems and computational complexity</a>. Theoretical Computer Science 81(2):317-324.</em></p>

<p>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).</p>

<p>You also have the following paper:</p>

<p><em>Christos Papadimitriou. <a href="http://www.cs.berkeley.edu/~christos/papers/On%20the%20Complexity.pdf" rel="nofollow">On the Complexity of the Parity Argument and Other Inefficient Proofs of Existence</a>. Journal of Computer and Systems Science 48(3), 1990.</em></p>

<p>In this paper you'll find: </p>

<ul>
<li>The $n$-dimensional Sperner's lemma,
which is a generalization of
Trichromatic Triangle.</li>
<li>Equilibrium of 2-player games.</li>
<li>Find a second hamiltonian path on a graph.</li>
</ul>

<p>The paper has a lot of examples of this type of problems. So I recommend to take a look at it.</p>

CC BY-SA 2.5
2011-02-08T09:03:07.363Z
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.
Oleksandr Bondarenko
CC BY-SA 2.5
2011-02-08T12:04:34.050Z
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?
Marcos Villagra
CC BY-SA 2.5
2011-02-08T16:20:20.980Z
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.
Hsien-Chih Chang 張顯之
CC BY-SA 2.5
2011-02-08T04:29:51.990Z
2011-02-09T04:01:20.083Z
2011-02-09T04:01:20.083Z
Marcos Villagra
<p>As an example, Shelby Kimmel uses the adversary method in <a href="http://arxiv.org/abs/1101.0797">this paper</a> 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}$.</p>

CC BY-SA 2.5
2011-02-08T00:37:16.553Z
2011-02-08T00:37:16.553Z
Artem Kaznatcheev
<p>Are there problems in CS where no efficient algorithms are known, despite existence theorems proving such efficient algorithms must exist?</p>

<p>What are these problems called? Where can I find out more?</p>

CC BY-SA 2.5
2011-02-08T01:35:37.657Z
What is your question? In the title says "solutions", but in the contents you write "algorithms".
Marcos Villagra
CC BY-SA 2.5
2011-02-08T10:03:40.383Z
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.
Kaveh
<ds.algorithms><reference-request><terminology>
Are there problems without efficient algorithms, where existence theorems have proved such algorithms must exist?
z5h
# Are there problems without efficient algorithms, where existence theorems have proved such algorithms must exist?

(Asked by: username_0 on 2011-02-07)

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?

**Tags:** ds.algorithms, reference-request, terminology
> **Comments:**
> **username_1**: What is your question? In the title says "solutions", but in the contents you write "algorithms".  
> **username_2**: 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.  

---

## 4 answers

### Answer by username_10 on 2011-02-08. Score: 9 | Accepted answer

As an example, Shelby Kimmel uses the adversary method in [this paper](http://arxiv.org/abs/1101.0797) 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}$.


---

### Answer by username_3 on 2011-02-07. Score: 13

Sure, there are lots of examples, at least in the spirit of your question.

Often one gets such a result from the [probabilistic method](http://en.wikipedia.org/wiki/Probabilistic_method). For example, one paper that I like that runs into the problem is on [reconstructing graphs in the additive model](http://hal.archives-ouvertes.fr/docs/00/07/35/17/PDF/RR-3171.pdf). 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.


---

### Answer by username_4 on 2011-02-07. Score: 2

No, you can always use [The fastest and the shortest algorithm for all well-defined problems](http://www.hutter1.net/ai/pfastprg.htm). ;)

> **Comments:**
> **username_4**: 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?  
> **username_5**: @Marcus Levin search requires the language in question to have a certificate. So at least those infinitely numerous "well defined" undecideable languages like EQUAL_TM escape Hutter-like Turing machine enumerating approaches. At the same time we know that any two TMs will accept the same language or not. (Note: I haven't read the paper in question and suspect he defines "well-defined" to mean 'has a certificate')  
> **username_5**: It should be added that in context of this question I think that Levin search is, in fact, a valid thing to discuss. So the comment above discussing Levin search and certificates isn't a criticism of this answer to this question. In fact I have upvoted it.  
> **username_6**: @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.  
> **username_5**: @Joshua Thank you Joshua. I'll have to delve through the Hutter paper, seeing how it doesn't appear to directly be a vanilla Levin search. I'm particularly interested in the following sentence of the abstract: "M avoids Blum's speed-up theorem by ignoring programs without correctness proof."  
> **username_5**: @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.  
> **username_7**: Is this algorithm the computational content of the equivalence of constructive and classical mathematics on forall-exists statements?  
> **username_4**: @Ross: wrt EQUAL_TM: yes, I should have argued the other way round: if we have an existence proof of an efficient algorithm as the question requires, then Hutter's search is an efficient algorithm. (With the possible exception that the time to compute the algorithm's time bound, Hutter $d_P\,\mathit{time}_{t_P}(x)$ term, makes it inefficient. I don't know if there's such an algorithm.)  
> **username_6**: @Neel Kirshnaswami: It's hard to say, since I didn't know there was such an equivalence! Can you give a pointer?  

---

### Answer by username_1 on 2011-02-08. Score: 1

**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](http://qwiki.stanford.edu/index.php/Complexity_Zoo%3aT#tfnp). It was defined in this paper:

*Nimrod Megiddo and Christos Papadimitriou. [On total functions, existence theorems and computational complexity](http://theory.stanford.edu/~megiddo/pdf/papadimX.pdf). 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](http://www.cs.berkeley.edu/~christos/papers/On%20the%20Complexity.pdf). 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.

> **Comments:**
> **username_8**: 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.  
> **username_1**: 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?  
> **username_9**: 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.  

---

