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 ...
Sasho Nikolov's user avatar
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 ...
Aryeh's user avatar
  • 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 ...
Gamow's user avatar
  • 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 ...
Bjørn Kjos-Hanssen's user avatar
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(...
mathworker21's user avatar
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/...
Aryeh's user avatar
  • 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. ...
ed kaye's user avatar
  • 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} $$ ...
StefanH's user avatar
  • 2,037

Only top scored, non community-wiki answers of a minimum length are eligible