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 ...
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 ...
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 ...
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 ...
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(...
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/...
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. ...
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}
$$
...
Only top scored, non community-wiki answers of a minimum length are eligible
Related Tags
computing-over-reals × 43cc.complexity-theory × 19
computability × 10
computable-analysis × 10
ds.algorithms × 7
reference-request × 5
na.numerical-analysis × 5
np-hardness × 3
time-complexity × 3
turing-machines × 3
complexity-classes × 2
approximation-algorithms × 2
cg.comp-geom × 2
reductions × 2
big-list × 2
np × 2
oracles × 2
algebraic-complexity × 2
approximation × 2
co.combinatorics × 1
optimization × 1
soft-question × 1
quantum-computing × 1
pl.programming-languages × 1
machine-learning × 1