New answers tagged

0 votes

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).
3 votes

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

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, ...
  • 10.5k

Top 50 recent answers are included