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 ...
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 ...
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 ...
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 \...
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 ...
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 ...
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 ...
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
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 ...
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 ...
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 × 41cc.complexity-theory × 18
computability × 10
computable-analysis × 10
ds.algorithms × 7
reference-request × 5
na.numerical-analysis × 5
np-hardness × 4
turing-machines × 3
complexity-classes × 2
cg.comp-geom × 2
np × 2
oracles × 2
open-problem × 2
algebraic-complexity × 2
approximation × 2
approximation-algorithms × 1
optimization × 1
soft-question × 1
quantum-computing × 1
time-complexity × 1
pl.programming-languages × 1
machine-learning × 1
lower-bounds × 1
counting-complexity × 1