Questions tagged [computing-over-reals]
The computing-over-reals tag has no usage guidance.
42
questions
4
votes
1
answer
180
views
Computing an approximate root of a two-dimensional monotone function
Let $f$ be a Lipschitz-continuous function from the square $[-1,1]^2$ to itself, satisfying the following conditions:
For all $y\in [-1,1]$: $~~~~f(-1,y)_1\leq 0\leq f(1,y)_1$, and $f(x,y)_1$ is ...
- 2,078
2
votes
0
answers
39
views
Statements equivalent to strongly polynomial time linear programming
Say a problem is SPT iff it admits an SPT algorithm. What statements of interest are known to be equivalent to "LP is SPT"? Examples:
"linear feasibility solving is SPT" (due to ...
- 652
1
vote
0
answers
147
views
Relation between BSS and Turing models
$P_\mathbb R$ is the set of languages decidable in polynomial time over the real $BSS$ machine defined in https://en.wikipedia.org/wiki/Blum%E2%80%93Shub%E2%80%93Smale_machine.
Let $0-1-P_\mathbb R=\{...
- 12.8k
6
votes
1
answer
147
views
Complexity of approximating a real function using queries
Consider the following computational problem, where $I$ is the real interval $[-1,1]$:
There is a monotonically-increasing function $f: I\to I$. You are allowed to access it only through queries of ...
- 2,078
5
votes
0
answers
86
views
Complexity of a specific class of definite integrals
INTRODUCTION: From the answer to this question I learned that deciding whether a definite integral is $0$ or not can be NP-complete, as the following integral representation of the Number Partition ...
- 181
4
votes
0
answers
193
views
A complexity-class of problems that cannot be solved in finite time
Is there a complexity class for problems such as the following?
Problem FindSum(s), where $s\in[0,1]$ is a real parameter:
Input: $g: [0,1]\to [0,1]$, a continuous monotone-increasing bijective ...
- 2,078
0
votes
1
answer
47
views
How can theoretical modelling be converted into viable product? [closed]
Many a times modelling is just for the sake of modelling like exploring some properties of materials which does not help in converting the theoretical modelling into a viable product that can serve ...
- 1
3
votes
1
answer
982
views
Examples of Fat-Shattering Dimension
What are some good examples for analysis of a class's Fat-Shattering dimension?
By (Alon et al) I know that the Fat-Shattering Dimension characterizes the learnability of real-valued function classes ...
- 168
2
votes
1
answer
97
views
Characterisation of computability of partial functions from infinite words into finite words by functions with prefix-free domain
The following is taken from K. Weihrauch, Computable Analysis, page 21. The notation $f : \subseteq A \to B$ means a partial function. By $\Sigma^{\omega}$ and $\Sigma^{\ast}$ we denote the set of ...
- 2,037
12
votes
2
answers
827
views
Euclidean TSP in NP and square root complexity
In this lecture notes by Ola Svensson: http://theory.epfl.ch/osven/courses/Approx13/Notes/lecture4-5.pdf, it is said that we don't know if Euclidean TSP is in NP:
The reason being that we do not ...
- 363
2
votes
0
answers
145
views
Are there analogues of Specker sequences for other complexity classes?
Consider the standard definition of computable real numbers: a real number $r$ is computable just in case $r$ is the limit of a sequence $(a_i)_{i \in \mathbb{N}}$ such that (1) the function $i \...
3
votes
1
answer
308
views
Zero of a multivariate cubic equation
Given a multivariate cubic equation $f(\vec{x})$ over reals where all coefficients of $f$ are integers, and a hyper-rectangle $B=\bigwedge_i x_i\in[a_i, b_i]$ where $a_i, b_i$ are constant integers, ...
- 1,345
4
votes
0
answers
249
views
NP Intermediate problems over Reals
While studying ${\bf NP}$ complete problems we have from Ladners' theorem - if ${\bf P}$ $\neq$ ${\bf NP}$-there are ${\bf NP}$ problems not in the class ${\bf P}$ nor ${\bf NP}$-complete. Ladners' ...
- 1,181
19
votes
3
answers
635
views
Computation of reals: floating point vs TTE vs domain theory vs etc
Currently, computation of reals in most popular languages is still done via floating point operations. On the other hand, theories like type two effectivity (TTE) and domain theory have long promised ...
- 523
2
votes
0
answers
151
views
Is the nonnegativeness of a polynomial hard for $\mathsf{NP}_\mathbb{R}$?
It is clear that the following problem is in $\mathsf{NP}_\mathbb{R}$.
Input: a list $P$ of triplets $(a,s,t)$
where $s$ and $t$ are nonnegative integers.
Output: is there an $x\in \mathbb{R}$ such ...
- 29
1
vote
1
answer
233
views
Is there any research on approximation of reals with computable numbers
I was wondering if there is any research in the field of Diophantine Approximation using the computable numbers. It seems to be a good fit, a dense countable set with a variety of different potential ...
- 127
1
vote
0
answers
117
views
Computing log of sum of positive integers
As input, we are give $k$-bit approximation (after the decimal point) of $\log(a)$ and $\log(b)$ for positive integers $a$ and $b$, i.e, we are given $\alpha$ and $\beta$ (as binary strings) as input ...
- 727
11
votes
2
answers
396
views
How to judge the definition of computational complexity of reals is natural or suitable?
As we know, definition of computational complexity of algorithm is almost without controversy, but the definition of computational complexity of reals or the computation models over reals is not in ...
- 1,058
9
votes
1
answer
330
views
Berman-Hartmanis Isomorphism for NP$_{\mathbb{R}}$?
Using the real-RAM/BSS model, we have the class NP$_{\mathbb{R}}$, (where a BSS is the Blum-Shub-Smale model of a computer with operations over reals). We have NP$_{\mathbb{R}}$ complete problems. ...
- 1,181
8
votes
1
answer
487
views
The exponential function over algebraic numbers
Given an algebraic number $\alpha$,
I am interested in finding an approximation of $\Re(e^\alpha)$
up to a given precision,
where $\Re()$ refers to the real part of the complex number.
Formally, I ...
- 181
16
votes
1
answer
1k
views
To what extent can the mathematics of Reals be applied to Computable Reals?
Is there a general theorem that would state, with proper sanitization,
that most known results regarding the use of real numbers can actually
be used when considering only computable reals? Or is ...
- 1,542
7
votes
1
answer
324
views
What complexity issues are there in considering quantum algorithms with infinite gate-sets?
Short Version
Suppose that you want to consider a model of quantum computation in which the gates used in the circuits may depend on the input size. Are there pitfalls to avoid when defining the ...
- 8,821
14
votes
1
answer
313
views
NP completeness over reals
I am studying the BSS model of computation recently (cf. for instance Complexity and Real Computation; Blum, Cucker, Shub, Smale.)
For reals $R$, it is shown that, given a system of polynomials $f_1,\...
- 1,345
2
votes
0
answers
96
views
Is this question $NP_R$ hard?
Consider $n$ variables $x_1, \cdots, x_n$ and
$f=\sum a_i x_1^{d_{i1}}\cdots x_n^{d_{in}}$ such that for each $i$, $d_{i1}+\cdots+d_{in}=d$ for some fixed $d$ and $a_i\geq 0$.
I am interested in the ...
- 1,345
8
votes
1
answer
457
views
Uniformity vs. nonuniformity in algebraic complexity theory
I understand that the study of Boolean circuits and nonuniform complexity classes was introduced to (hopefully) prove separation of uniform complexity classes. In this sense, nonuniform computational ...
- 895
1
vote
2
answers
335
views
Foundational textbook(s) for Complexity and Computability on Real Numbers
It would be extremely helpful if someone can suggest foundational textbooks on Recursive Analysis (Computability over Reals) which explains connections between Computability and the Topological ...
- 265
6
votes
3
answers
1k
views
Computing Functions with Dynamical Systems
I was trying to make a set of differential equations "compute" some given function just like a Turing Machine does. Essentially, a given Turing Machine with an initial configuration (which includes ...
- 161
22
votes
5
answers
5k
views
Is it possible to test if a computable number is rational or integer?
Is it possible to algorithmically test if a computable number is rational or integer?
In other words, would it be possible for a library that implements computable numbers to provide the functions <...
- 355
6
votes
2
answers
379
views
Oracle complexity of a problem in the Counting Hierarchy
In "On The Complexity of Numerical Analysis" (SIAM J. Comp. Vol. 38, 2009), Allender et al. introduce the problem of PosSLP and show that its complexity lies in the counting hierarchy, and more ...
- 497
1
vote
1
answer
298
views
Concerning decidability of a problem on real numbers [closed]
This question is an outgrowth of a certain maths problem I've been thinking about.
Suppose you use an oracle to represent a real number. The oracle is of the following form: you give it an integer ...
- 119
18
votes
2
answers
7k
views
Complexity of computing the discrete Fourier transform?
What is the complexity (on the standard integer RAM) of computing the standard discrete Fourier transform of a vector of $n$ integers?
The classical algorithm for fast Fourier transforms, ...
- 23.1k
2
votes
0
answers
81
views
mean/integral, except where positive differences between values and "mean" are weighted differently from negative differences?
Given a curve $f(x)$ (for $x \in [0,1]$), and a line $y=a$, let $U$ be the total area below $f$ and above $a$, and let $L$ be the total area above $f$ and below $a$. If $L=U$, this means that $a =\...
- 21
10
votes
1
answer
193
views
Reference for the undefinability of modulus of continuity functional in PCF?
Can someone point me to the reference for the non-definability of the modulus of continuity functional in PCF? $\newcommand{\N}{\mathbb{N}}$ $\newcommand{\bool}{\mathsf{bool}}$
Andrej Bauer has ...
- 32.4k
6
votes
2
answers
520
views
Iterative algorithms in algebraic complexity (Blum-Shub-Smale-Model)
I know the Blum-Shub-Smale model. It is claimed to provide a theoretical framework for algorithms in real and complex algebra and analysis.
A very general question:
Most algorithms compromise of
...
- 1,165
1
vote
1
answer
170
views
Using a Polynomial Time Algorithm for Upper Bound Recognition to Show Polynomial Time for Evaluation?
Let's say I had an optimization problem
$$ \min_{x \in D} f(x) $$
Where $D \subset \mathbb{R}^n$ and $f:\space D \rightarrow \mathbb{R}$, and the minimum is said to exist.
Imagine I had a ...
- 113
41
votes
2
answers
6k
views
Sum-of-square-roots-hard problems?
The sum of square roots problem asks, given two sequences $a_1, a_2, \dots, a_n$ and $b_1, b_2, \dots, b_n$ of positive integers, whether the sum $\sum_i \sqrt{a_i}$ less than, equal to, or greater ...
- 23.1k
22
votes
1
answer
1k
views
Complexity of computing shortest paths in the plane with polygonal obstacles
Suppose we are given several disjoint simple polygons in the plane, and two points $s$ and $t$ outside every polygon. The Euclidean shortest path problem is to compute the Euclidean shortest path ...
- 23.1k
16
votes
2
answers
5k
views
Time complexity of Bellman-Held-Karp algorithm for TSP, take 2
A recent question discussed the now-classical dynamic programming algorithm for TSP, due independently to Bellman and Held-Karp. The algorithm is universally reported to run in $O(2^n n^2)$ time. ...
- 23.1k
31
votes
3
answers
2k
views
Consequences of existence of a strongly polynomial algorithm for linear programming?
One of the holy grails of algorithm design is finding a strongly polynomial algorithm for linear programming, i.e., an algorithm whose runtime is bounded by a polynomial in the number of variables and ...
- 2,717
43
votes
3
answers
4k
views
What are the reasons that researchers in computational geometry prefer the BSS/real-RAM model?
Background
The computation over real numbers are more complicated than computation over natural numbers, since real numbers are infinite objects and there are uncountably many real numbers, therefore ...
- 21.5k
27
votes
6
answers
2k
views
How are real numbers specified in computation?
This may be a basic question, but I've been reading and trying to understand papers on such subjects as Nash equilibrium computation and linear degeneracy testing and have been unsure of how real ...
user1338
1
vote
3
answers
921
views
Complexity of a variant of the Mandelbrot set decision problem?
Mandelbrot set is defined using the complex equation $P_c (z)=z^2 +c$ where $c$ is a complex number
Let Set $M=${$(c,k,m) |$ the sequence $P_c (0),P_c (P_c (0)), P_c (P_c (P_c (0)))...$ is unbounded ...
- 20.8k