# Tag Info

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.2k

### 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.6k

### 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,485

• 321
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.6k
1 vote
Accepted

### What infinite sums cannot be approximated in polynomial time?

OP asks (now in the comments) for a real number $s$ such that (among other things), one can prove that, if the first $n$ bits of $s$ can be computed in time poly$(n)$, then P$=$NP. Perhaps the most ...
• 10.8k
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,077
1 vote

### Is it possible to test if a computable number is rational or integer?

As a (hopefully fun) exercise, we pin down the complexities of the two problems more precisely. Let $x$ be a given computable number (encoded as defined in the post). Lemma 1. The problem of ...
• 10.8k

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