Skip to main content
OverflowAI is here! AI power for your Stack Overflow for Teams knowledge community. Learn more
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.6k
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
4 votes

Deciding whether a convex region is empty

Warning: As one of the comments points out, the sum of squares is not necessarily convex, so the hardness reduction suggested below does not work. The problem still lies in $\exists\mathbb{R} \...
user67422's user avatar
  • 144
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
3 votes
Accepted

Maximum theoretical compression ratio for real-valued data

With the problem as stated, you can compress the $N$ real-valued vectors into $K$ real-valued vectors, and reconstruct the original $N$ vectors exactly. How does this work? Suppose you want to ...
Peter Shor '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.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 ...
Neal Young's user avatar
  • 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. ...
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,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 ...
Neal Young's user avatar
  • 10.8k

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