# Questions tagged [computing-over-reals]

The tag has no usage guidance.

42 questions
Filter by
Sorted by
Tagged with
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 ...
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 ...
1 vote
147 views

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, ...
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' ...
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 ...
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 ...
1 vote
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 ...
1 vote
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 ...
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 ...
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. ...
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 ...
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 ...
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 ...
313 views

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 ...
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 vote
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 ...
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 ...
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 ...
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. ...
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 ...
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 ... 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 ...