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 ...
user avatar
17 votes

Computation of reals: floating point vs TTE vs domain theory vs etc

I work in real-number computation, and I wish I knew the real answer. But I can speculate. It's a sociological problem, I think. The community of people who work on exact real arithmetic consists of ...
user avatar
  • 26.6k
16 votes
Accepted

To what extent can the mathematics of Reals be applied to Computable Reals?

The real numbers may be characterized in a couple of ways, let us work with the Cauchy-complete archimedean ordered field. (We need to be a bit careful how exactly we say this, see Definition 11.2.7 ...
user avatar
  • 26.6k
13 votes

How to judge the definition of computational complexity of reals is natural or suitable?

I am not exactly sure what the question is here, but I can try to say a bit to clean up possible misunderstandings. First of all, if we are talking about complexity of a map $f : \mathbb{R} \to \...
user avatar
  • 26.6k
10 votes

Computation of reals: floating point vs TTE vs domain theory vs etc

In general, people always care about floating point errors. However I disagree with Andrej, and I do not think that floats are preferred to arbitrary precision reals (for the most part) because of ...
user avatar
  • 13.2k
8 votes
Accepted

Berman-Hartmanis Isomorphism for NP$_{\mathbb{R}}$?

Depending on which version of $\mathsf{NP}_{\mathbb{R}}$ you use, yes or it's open. When one considers BSS machines that only use addition and subtaction, and only branch on equality, the answer is ...
user avatar
6 votes

What complexity issues are there in considering quantum algorithms with infinite gate-sets?

To answer my own question: for the purposes of exact computation, there's no need to worry about having too much computational power from linear combinations of algebraic numbers. Details On ...
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 ...
user avatar
  • 10k
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 ...
user avatar
  • 5,712
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 ...
user avatar
3 votes

The exponential function over algebraic numbers

As written, the problem requires time $2^{\Omega(m)}$, where $m$ is the length of input (you unfortunately used $n$ for something else). Indeed, if e.g. $\alpha$ is a positive integer (given by its ...
user avatar
3 votes

How to judge the definition of computational complexity of reals is natural or suitable?

Another model possibly to explore, is that of the Feasible RAM model. This is a modified real RAM model for Real computation, Feasible RAM, or a modified RAM model which uses both the discrete, and ...
user avatar
  • 1,081
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/...
user avatar
  • 10k
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. ...
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} $$ ...
user avatar
  • 1,947

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