# Tag Info

### Flow of value lower bounded by $X$

SHORT ANSWER Probably not, or at least a solution running in such a time is not known to this date. ARGUMENT According to Wikipedia's review of Chen et al.'s article on arXiv, the ultimate state of ...
• 2,590
1 vote

### Examples of promise search problems that are easier than their non-promise variants?

The search problem “given a Turing machine that terminates, compute its output” is computable, but it is not computable without the promise (it is as hard as the halting problem).
• 14.9k
Assuming that you can efficiently verify that any proposed solution is valid, no such problem exists. There's a trivial reduction. Suppose there was an algorithm $A$ that made use of the promise, ...