New answers tagged ds.algorithms
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).
- 14.9k
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