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 ...
- 18k
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 ...
- 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 ...
- 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 \...
- 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 ...
- 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 ...
- 35.7k
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 ...
- 8,821
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 ...
- 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 ...
- 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 ...
- 4,400
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 ...
- 14.8k
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 ...
- 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/...
- 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. ...
- 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}
$$
...
- 1,947
Only top scored, non community-wiki answers of a minimum length are eligible