19
votes
Accepted
Euclidean TSP in NP and square root complexity
Q1. This is a notorious open problem. It is known to be in the fourth level of the counting hierarchy, due to [ABKM]. Not known to be in NP. The problem is not really in computing square roots as ...
- 18.1k
4
votes
Complexity of approximating a real function using queries
Not a complete answer, but hopefully a good starting point. It is very instructive to (always!) first consider the discrete analog of your question. If $X$ is some set and $f:X\to\{0,1\}$, what is the ...
- 10.3k
4
votes
Euclidean TSP in NP and square root complexity
You wrote:
On the other hand there is this paper by Papadimitriou: http://www.sciencedirect.com/science/article/pii/0304397577900123 saying it is NP-complete, which also means it is in NP. Although ...
- 5,772
4
votes
Is there any research on approximation of reals with computable numbers
It's funny you should ask, because computability and diophantine approximation has actually been a popular topic in recent years. In particular Becher and Slaman and coauthors have many results and ...
- 4,475
3
votes
Accepted
Computing an approximate root of a two-dimensional monotone function
Yes, it's possible with $O\left(\log^2(1/\epsilon)\right)$ function evaluations.
We write $f = (f_1,f_2)$, so in your notation, e.g. $f_1(x,y) := f(x,y)_1$. By replacing $f_1$ with $(x,y) \mapsto f_1(...
- 321
2
votes
Accepted
Examples of Fat-Shattering Dimension
For $L$-Lipschitz functions on a metric space $(X,\rho)$ with $\epsilon$-packing number $M(\epsilon)$, the $\gamma$-shattering dimension is $M(2\gamma/L)$, as proved here:
http://ieeexplore.ieee.org/...
- 10.3k
1
vote
How can theoretical modelling be converted into viable product?
I'm assuming that you're really asking, "how do I do something useful with modelling and theory."
The easiest answer is to work in a modelling and simulation field that makes useful products. ...
- 11
1
vote
Accepted
Characterisation of computability of partial functions from infinite words into finite words by functions with prefix-free domain
I guess I have an alternative solution. Let $f :\subseteq \Sigma^{\omega} \to \Sigma^{\omega}$ be computable. Define
$$
h(u) = v \mbox{ iff }
f(u\Sigma^{\omega}) = \{v\} \mbox{ with $u$ minimal}
$$
...
- 2,037
Only top scored, non community-wiki answers of a minimum length are eligible